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

https://gyazo.com/b2df8c9ce8cf3c362ec03a2b2839fd8b

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

https://gyazo.com/68fc51e0aad6ed0f251979427ce9fbfe

$ 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}