パスカルの三角形に現れるフィボナッチ数列
$n \geq 0$ とする。フィボナッチ数列 $\{F_n\}$ （ただし $F_1=F_2=1$）について, 次の等式が成り立つ。 $$ F_{n+1} = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} {}_{n-k}\mathrm{C}_k $$ 等式の右辺は, パスカルの三角形（下図）において, 上から $n$ 本目 $(n \geq 0)$ の直線状の数の和に対応している。
$\displaystyle a_n = \sum_{k=0}^{\lfloor n/2 \rfloor} {}_{n-k}\mathrm{C}_k$ とおき, これがフィボナッチ数列の定義 $a_n = a_{n-1} + a_{n-2}$ および $a_1 = a_2 = 1$ を満たすことを示す。
$n=0$ のとき, $a_0 = {}_{0}\mathrm{C}_0 = 1 = F_1$
$n=1$ のとき, $a_1 = {}_{1}\mathrm{C}_0 = 1 = F_2$
となり, フィボナッチ数列の初期条件と一致する。
ある直線上の $k$ 番目の数を ${}_{n-k}\mathrm{C}_k$ とすると, 次の数は段を1つ下げ（$n$を増やす）, 右へ1つずらす（$k$を増やす）ことで得られる。 このとき, 二項係数が定義される条件 $n-k \geq k$ より $k \leq n/2$ が導かれ, $\displaystyle \sum_{k=0}^{\lfloor n/2 \rfloor} {}_{n-k}\mathrm{C}_k$ はパスカルの三角形を斜めに結んだ数の和であることが確認できる。
以下, $n \geq 2$ として, $a_{n} = a_{n-1} + a_{n-2}$ であることを示す。
$n$ が偶数の場合, $\ell$ を整数として $n=2 \ell$ とする. このとき,
$\begin{aligned}
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
\end{aligned}$
$\begin{aligned}
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
\end{aligned}$
$\begin{aligned}
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
\end{aligned}$
である。
$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$ が奇数の場合も同様に $a_n = a_{n-1} + a_{n-2}$ が成り立つ。
ゆえに, $a_n$ はフィボナッチ数列の定義 $a_n = a_{n-1} + a_{n-2}$ および初期値 $a_0=1, a_1=1$ を満たす。 したがって, $a_n = F_{n+1}$ が成り立つ。
