Sum of binomial coefficients and Fibonacci

${\sum }_i\left(\genfrac{}{}{0ex}{}{N-i}{i}\right)=F_N$

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

$F_N={\sum }_{i\ge 0}\left(\genfrac{}{}{0ex}{}{N-i}{i}\right)=1+{\sum }_{i\ge 1}\left(\genfrac{}{}{0ex}{}{N-i}{i}\right)$ $=1+{\sum }_{i\ge 1}\left(\left(\genfrac{}{}{0ex}{}{N-i-1}{i}\right)+\left(\genfrac{}{}{0ex}{}{N-i-1}{i-1}\right)\right)$ $=1+{\sum }_{i\ge 1}\left(\genfrac{}{}{0ex}{}{N-i-1}{i}\right)+{\sum }_{i\ge 1}\left(\genfrac{}{}{0ex}{}{N-i-1}{i-1}\right)$ $=1+{\sum }_{i\ge 1}\left(\genfrac{}{}{0ex}{}{N-i-1}{i}\right)+{\sum }_{j\ge 0}\left(\genfrac{}{}{0ex}{}{N-j-2}{j}\right)$ $={\sum }_{i\ge 0}\left(\genfrac{}{}{0ex}{}{N-i-1}{i}\right)+{\sum }_{j\ge 0}\left(\genfrac{}{}{0ex}{}{N-j-2}{j}\right)$ $={\sum }_{i\ge 0}\left(\genfrac{}{}{0ex}{}{(N-1)-i}{i}\right)+{\sum }_{i\ge 0}\left(\genfrac{}{}{0ex}{}{(N-2)-i}{i}\right)$ $=F_{N-1}+F_{N-2}$

• binomial coefficient and Fibonacci series

---

This page is auto-translated from /nishio/二項係数の和とフィボナッチ using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.