算術三角形からフィボナッチ数列を作る

算術三角形は普通下図のように描かれる。算術三角形
これからフィボナッチ数列を作るには、以下のように斜めにし、縦に並んだところで足すとわかりやすい。算術三角形とフィボナッチ数列

証明するには、算術三角形を組合せの数で見てあげると良い。

フィボナッチ数列 $(F_{n})$ は組合せの数 $_{n} C_{r}$ により以下のように表せる。ただし $[x]$ は $x$ 以下の最大の整数を表す。 $F_{n} = \sum_{r = 0}^{[\frac{n - 1}{2}]}_{n - r - 1} C_{r}$

$\sum_{r = 0}^{[\frac{n - 1}{2}]}_{n - r - 1} C_{r}$ がフィボナッチ数列の漸化式を満たせばよい。
$F_{1}, F_{2}$ について
$\begin{array}{r} \sum_{r = 0}^{[\frac{1 - 1}{2}]}_{1 - r - 1} C_{r} =_{0} C_{0} = 1 \\ \sum_{r = 0}^{[\frac{2 - 1}{2}]}_{2 - r - 1} C_{r} =_{1} C_{0} = 1 \end{array}$
$n$ が偶数のとき $n = 2 m$ なる整数 $m$ が在って
$\begin{aligned} \sum_{r = 0}^{[\frac{n - 1}{2}]}_{n - r - 1} C_{r} + \sum_{r = 0}^{[\frac{n}{2}]}_{n - r} C_{r} & = \sum_{r = 0}^{m - 1}_{2 m - r - 1} C_{r} + \sum_{r = 0}^{m}_{2 m - r} C_{r} \\ = \sum_{r = 1}^{m}_{2 m - r} C_{r - 1} + \sum_{r = 1}^{m}_{2 m - r} C_{r} +_{2 m} C_{0} \\ = \sum_{r = 1}^{m} (_{2 m - r} C_{r - 1} +_{2 m - r} C_{r}) +_{2 m + 1} C_{0} \\ = \sum_{r = 0}^{m}_{2 m - r + 1} C_{r} = \sum_{r = 0}^{[\frac{n + 1}{2}]}_{n - r + 1} C_{r} \end{aligned}$
$n$ が奇数のとき $n = 2 m + 1$ なる整数 $m$ が在って
$\begin{aligned} \sum_{r = 0}^{[\frac{n - 1}{2}]}_{n - r - 1} C_{r} + \sum_{r = 0}^{[\frac{n}{2}]}_{n - r} C_{r} & = \sum_{r = 0}^{m}_{2 m - r} C_{r} + \sum_{r = 0}^{m}_{2 m - r + 1} C_{r} \\ =_{m} C_{m} + \sum_{r = 0}^{m - 1}_{2 m - r} C_{r} + \sum_{r = 1}^{m}_{2 m - r + 1} C_{r} +_{2 m - 1} C_{0} \\ =_{m + 1} C_{m + 1} + \sum_{r = 1}^{m}_{2 m - r + 1} C_{r - 1} + \sum_{r = 1}^{m}_{2 m - r + 1} C_{r} +_{2 m} C_{0} \\ = \sum_{r = 0}^{m + 1}_{2 m - r + 2} C_{r} = \sum_{r = 0}^{[\frac{n + 1}{2}]}_{n - r + 1} C_{r} \end{aligned}$