パスカルの三角形の中のフィボナッチ数列

解説.

$a_n=\displaystyle \sum_{k=0}^{[\frac{n}{2}]}{}_{n-k} \mathrm{C}_k$ とする.

---

まず, $\{a_n\}_{n \leq 0}$ がパスカルの三角形に引いた $n$ 番目の直線上の数の和を表していることを示す.

$a_0=\displaystyle \sum_{k=0}^{0}{}_{0-k} \mathrm{C}_k$ $={}_0\mathrm{C}_0$ であるため, $a_0=1=F_1$ である.

$a_1=\displaystyle \sum_{k=0}^{0}{}_{1-k} \mathrm{C}_k$ $={}_1\mathrm{C}_0$ であるため, $a_1=1=F_2$ である.

さて, $n \geq 2$ として, $a_n$ の式を作る.

ある直線上の数のうち最も左の数が ${}_n\mathrm{C}_0$ であるとき, 直線上の次の数は「１つ上の段の１つ右の数」である. これは, ${}_{n-1} \mathrm{C}_1$ である.

同様に次の数は, ${}_{n-2}\mathrm{C}_2$ である. $k$ $(\geq 0)$ 番目の数は ${}_{n-k}\mathrm{C}_k$ である.

この数は $n-k \geq k$ である限り, パスカルの三角形上の数を表す. したがって, $\displaystyle k \leq \frac{n}{2}$ が必要である.

ゆえに, $\displaystyle \sum_{k=0}^{[\frac{n}{2}]}{}_{n-k} \mathrm{C}_k$ が直線上にある数の和を表すことが分かる.

---

次に, $n \geq 2$ として, $a_{n} = a_{n-1} + a_{n-2}$ であることを示す.

$n$ が偶数の場合, $\ell$ を整数として $n=2 \ell$ とする. このとき,

$a_n$ $\displaystyle =\sum_{k=0}^{\ell}{}_{2\ell-k} \mathrm{C}_k$ $\displaystyle = {}_{2\ell}\mathrm{C}_0 +\sum_{k=1}^{\ell-1}{}_{2\ell-k} \mathrm{C}_k+{}_{\ell} \mathrm{C}_\ell$ $\displaystyle = 2 +\sum_{k=1}^{\ell-1}{}_{2\ell-k} \mathrm{C}_k$

$a_{n-1}$ $\displaystyle =\sum_{k=0}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle ={}_{2\ell-1}\mathrm{C}_0+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle =1+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$

$a_{n-2}$ $\displaystyle =\sum_{k=0}^{\ell-1}{}_{(2\ell-2)-k} \mathrm{C}_k$ $\displaystyle =\sum_{k=1}^{\ell}{}_{(2\ell-2)-(k-1)} \mathrm{C}_{k-1}$ $\displaystyle =\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+{}_{\ell-1} \mathrm{C}_{\ell-1}$ $\displaystyle =\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+1$

である.

$a_{n-1}+a_{n-2}$ を計算すると,

$\displaystyle 1+\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_k$ $\displaystyle +\sum_{k=1}^{\ell-1}{}_{(2\ell-1)-k} \mathrm{C}_{k-1}+1$

$=\displaystyle 2+\sum_{k=1}^{\ell-1} \{{}_{(2\ell-1)-k}\mathrm{C}_k +{}_{(2\ell-1)-k} \mathrm{C}_{k-1} \}$

となる. 次の関係式を利用して, さらに計算すると,

${}_n\mathrm{C}_r +{}_n\mathrm{C}_{r+1} = {}_{n+1}\mathrm{C}_{r+1}$

$\displaystyle 2+\sum_{k=1}^{\ell-1} {}_{2\ell-k}\mathrm{C}_k$

となり, $a_n$ の式と等しいことが分かる.

また, $n$ が奇数のときも同様の議論が成り立つ.

以上から, $n\geq 2$ のとき, $a_{n} = a_{n-1}+a_{n-2}$ かつ $a_1=a_0=1$ であるから, $a_n = F_{n+1}$ である.