(3)の別解Ⅱ
1から $n$ まで異なる番号のついた $n$ 個のボールを，区別のつかない3つの箱に入れる場合，その入れ方は全部で何通りあるか。空箱があってもよい。
ヒロ
次は漸化式を利用した解法も説明しておこう。
求める場合の数を $a_n$ として，$n$ 個のボールを入れた状態から $n+1$ の番号のついたボール（ボールAとする）の入れ方を考える。
$n=1$ のときは，箱を区別しないからボールの入れ方は1通りしかないから $a_1=1$ となる。
また，$n=2$ のときは，1つの箱に2個とも入れるか，2つの箱に1個ずつ入れるかの2通りあるから $a_2=2$ となる。
$n$ 個のボールを入れた状態には，
(i) 2つの箱が空のとき（1通り）
(ii) (i)以外のとき（$a_n-1$ 通り）
の2種類の状態がある。
(i)のとき，ボールAの入れ方としては，$n$ 個のボールが入っている箱に入れるか，空の箱に入れるかの2通りがある。
(i)以外のときのボールAの入れ方は，3つの箱のうち，どの箱に入れるかを考えて3通りある。
(ii)のときが起こるのが $n$ が2以上のときだから $n\geqq2$ のとき
①より，
$n=1$ のときは，箱を区別しないからボールの入れ方は1通りしかないから $a_1=1$ となる。
また，$n=2$ のときは，1つの箱に2個とも入れるか，2つの箱に1個ずつ入れるかの2通りあるから $a_2=2$ となる。
$n$ 個のボールを入れた状態には，
(i) 2つの箱が空のとき（1通り）
(ii) (i)以外のとき（$a_n-1$ 通り）
の2種類の状態がある。
(i)のとき，ボールAの入れ方としては，$n$ 個のボールが入っている箱に入れるか，空の箱に入れるかの2通りがある。
(i)以外のときのボールAの入れ方は，3つの箱のうち，どの箱に入れるかを考えて3通りある。
(ii)のときが起こるのが $n$ が2以上のときだから $n\geqq2$ のとき
\begin{align*}
&a_{n+1}=1\Cdota2+(a_n-1)\Cdota3 \\[4pt]
&a_{n+1}=3a_n-1~\cdots\cdots ①
\end{align*}
が成り立つ。ここで，$a_1=1,~a_2=2$ だから①は $n=1$ のときも成り立つ。&a_{n+1}=1\Cdota2+(a_n-1)\Cdota3 \\[4pt]
&a_{n+1}=3a_n-1~\cdots\cdots ①
\end{align*}
①より，
\begin{align*}
a_{n+1}-\dfrac{1}{2}=3\left(a_n-\dfrac{1}{2}\right)
\end{align*}
数列$\left\{a_n-\dfrac{1}{2}\right\}$ は初項 $a_1-\dfrac{1}{2}=\dfrac{1}{2}$，公比3の等比数列となるから，a_{n+1}-\dfrac{1}{2}=3\left(a_n-\dfrac{1}{2}\right)
\end{align*}
\begin{align*}
&a_n-\dfrac{1}{2}=\dfrac{1}{2}\Cdota3^{n-1} \\[4pt]
&a_n=\dfrac{3^{n-1}+1}{2}
\end{align*}
よって，求める入れ方は全部で $\dfrac{3^{n-1}+1}{2}$ 通り。&a_n-\dfrac{1}{2}=\dfrac{1}{2}\Cdota3^{n-1} \\[4pt]
&a_n=\dfrac{3^{n-1}+1}{2}
\end{align*}