2018年入試問題研究に戻るお茶の水大解答
(1)
解１ \begin{eqnarray*} (x+1)(x+1)^{n-1}&=&(1+x)\left(x^{n-1}+\cdots+{}_{n-1} \mathrm{C}_r x^r+{}_{n-1} \mathrm{C}_{r-1} x^{r-1}+\cdots+1\right)\\ &=&x^n+\cdots+\left({}_{n-1} \mathrm{C}_r +{}_{n-1} \mathrm{C}_{r-1}\right) x^r+\cdots+1 \end{eqnarray*} なので， $ (x+1)^n=(x+1)(x+1)^{n-1} $ の両辺の $ x^r $ の係数を比較することにより， $ 1\le r \le n-1 $ を満たす自然数 $ r $ に対し， \[ {}_n \mathrm{C}_r={}_{n-1} \mathrm{C}_r+{}_{n-1} \mathrm{C}_{r-1} \] が成り立つ．
解２
$ n $ 個の区別されたものから $ r $ 個選ぶ選び方を， 特定のものが含まれない選び方と特定のものが含まれる選び方に分ける．
1) 特定のものが含まれない選び方は，特定のものを除く $ n-1 $ 個から $ r $ 個選ぶので， $ {}_{n-1} \mathrm{C}_r $ 通りある．
2) 特定のものが含まれる選び方は， 特定のものをを除く $ n-1 $ 個から $ r-1 $ 個選び特定のものを加えればよいので， $ {}_{n-1} \mathrm{C}_{r-1} $ 通りある．
$ n $ 個の区別されたものから $ r $ 個選ぶ $ {}_n \mathrm{C}_r $ 通りの選び方は，このいずれかに分けられるので， \[ {}_n \mathrm{C}_r={}_{n-1} \mathrm{C}_r+{}_{n-1} \mathrm{C}_{r-1} \] が成り立つ．解３ \begin{eqnarray*} {}_{n-1} \mathrm{C}_r+{}_{n-1} \mathrm{C}_{r-1}&=& \dfrac{(n-1)!}{(n-1-r)!r!}+\dfrac{(n-1)!}{(n-r)!(r-1)!}\\ &=&\dfrac{(n-1)!(n-r)+(n-1)!r}{(n-r)!r!}=\dfrac{n!}{(n-r)!r!}={}_n \mathrm{C}_r \end{eqnarray*} である．
(2) $ n=1 $ のとき， $ F_{1+1}=F_2=1 $ ． $ \left[\dfrac{1}{2}\right]=0 $ なので，右辺も1で成り立つ．
$ n=2 $ のとき， $ F_{1+2}=F_3=F_2+F_1=2 $ ． $ \left[\dfrac{2}{2}\right]=1 $ なので， \[ 右辺={}_{2-0} \mathrm{C}_0+{}_{2-1} \mathrm{C}_1=1+1=2 \] で成り立つ．(3) $ r>n $ のとき， $ {}_n \mathrm{C}_r=0 $ と定める．このとき $ (★) $ は \[ F_{n+1}=\sum_{r=0}^{n-1}{}_{n-r} \mathrm{C}_r \quad \cdots(*) \] となる．これを数学的帰納法で示す． (2)と同様に $ n=1,\ 2 $ で $ (*) $ は成り立つ．
そして， $ n $ ， $ n-1 $ で $ (*) $ が成り立つと仮定する． $ n\geqq 3 $ のとき， \begin{eqnarray*} F_{n-1}&=&\sum_{r=0}^{n-3}{}_{n-2-r} \mathrm{C}_r\\ F_{n}&=&\sum_{r=0}^{n-2}{}_{n-1-r} \mathrm{C}_r =1+\sum_{r=1}^{n-2}{}_{n-1-r} \mathrm{C}_r =1+\sum_{r=0}^{n-3}{}_{n-2-r} \mathrm{C}_{r+1} \end{eqnarray*} である．よって， \begin{eqnarray*} F_{n}+F_{n-1}&=&1+\sum_{r=0}^{n-3}\left({}_{n-2-r} \mathrm{C}_{r+1}+{}_{n-2-r} \mathrm{C}_r \right)\\ &=&1+\sum_{r=0}^{n-3}{}_{n-1-r} \mathrm{C}_{r+1}=1+\sum_{r=1}^{n-2}{}_{n-r} \mathrm{C}_{r}\\ &=&\sum_{r=0}^{n-2}{}_{n-r} \mathrm{C}_{r}=\sum_{r=0}^{n-1}{}_{n-r} \mathrm{C}_{r}=F_{n+1} \end{eqnarray*} となり， $ (*) $ は $ n+1 $ でも成り立つ． 数学的帰納法によりすべての $ n $ で $ (*) $ が成り立つ．
これより，すべての $ n $ で $ (★) $ が成り立つ．