二項係数の和とフィボナッチ

$\sum_i \binom{N-i}{i} = F_N$

• where $F_0 = F_1 = 1, F_n = F_{n-2} + F_{n-1}$

$F_N = \sum_{i\ge 0} \binom{N-i}{i} = 1 + \sum_{i\ge 1} \binom{N-i}{i}$ $= 1 + \sum_{i \ge 1} \left(\binom{N-i - 1}{i} + \binom{N-i - 1}{i-1}\right)$ $= 1 + \sum_{i \ge 1} \binom{N-i - 1}{i} + \sum_{i \ge 1} \binom{N-i - 1}{i-1}$ $= 1 + \sum_{i \ge 1} \binom{N-i - 1}{i} + \sum_{j \ge 0} \binom{N - j - 2}{j}$ $= \sum_{i \ge 0} \binom{N-i - 1}{i} + \sum_{j \ge 0} \binom{N - j - 2}{j}$ $= \sum_{i \ge 0} \binom{(N-1) - i}{i} + \sum_{i \ge 0} \binom{(N-2) - i}{i}$ $= F_{N-1} + F_{N-2}$

二項係数とフィボナッチ数列