Förberedande kurs i matematik

Låt oss sätta

\displaystyle \qquad f_n = \sum_{k=0}^n {n-k+1 \choose k} .

Vi ser nu att \displaystyle f_0 = 1 , och att

\displaystyle \qquad f_1 = \sum_{k=0}^1 {2-k \choose k} = {2 \choose 0} + {1 \choose 1} = 2 .

Nu, notera att eftersom

\displaystyle \qquad{n - k \choose k} = {n - k-1 \choose k-1} + {n-k-1 \choose k}

så gäller att

\displaystyle \qquad\begin{align}f_n &= \sum_{k=0}^n {n-k-1 \choose k} =\\&= \sum_{k=0}^n {n-k-2 \choose k-1}+ {n - k-2 \choose k} =\\&= \sum_{k=0}^{n-1} {n-k-1 \choose k} + \sum_{k=0}^{n-2} {n -k-2 \choose k} =\\&= f_{n-1} + f_{n-2}\end{align}.

Men , eftersom att \displaystyle f_0 var ju 1, och och \displaystyle f_1 var 2, det andra resp. tredje fibonaccitalet. Men då , eftersom \displaystyle f_n = f_{n-1}+f_{n-2} måste ju \displaystyle f_n vara det n+1 första Fibonaccitalet.