Generating Function Fibonacci Numbers

fibonacci Sequence Formula

Binet Formula for Fibonacci Sequence

While there are many ways to derive the recursive formula of Fibonacci Sequence. The formula to find the nth term of a Fibonacci sequence is a beautiful formula. We are not going to derive here but prove the formula using mathematical Induction
We use Strong Induction to prove the Binet Formula because we will be invoking the recursive formula of fibonacci sequence to prove the $n+1$ case.
The Binet formula is $\frac{\phi^n-\alpha^n}{\sqrt{5}}$ $\phi = \frac{1+\sqrt{5}}{2}$ and $\alpha = \frac{1-\sqrt{5}}{2}$.
Verify the base cases: for $n = 1$ we have $\frac{\phi-\alpha}{\sqrt{5}}= 1$

Similarly for $n = 2$ we have $\frac{\phi^2-\alpha^2}{\sqrt{5}}$
$\Rightarrow \frac{(\phi-1)-(\alpha-1)}{\sqrt{5}}$
$\Rightarrow \frac{\phi-\alpha}{\sqrt{5}}$
which we know from first statement is true To prove the last step we realize that $F_{n+1}=F_n+F_{n-1}$
Thus we have $\Rightarrow F_{n+1}= \frac{\phi^n-\alpha^n}{\sqrt{5}}+\frac{\phi^{n-1}-\alpha^{n-1}}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^n+\phi^{n-1}-\alpha^n-\alpha^{n-1}}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi+1)-\alpha^{n-1}(\alpha+1)}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n-1}(\phi^2)-\alpha^{n-1}(\alpha^2)}{\sqrt{5}}$
$\Rightarrow F_{n+1}= \frac{\phi^{n+1}-\alpha^{n+1}}{\sqrt{5}}$
Hence Proved

Fibonacci Number thorugh Combinatorics

Here is one way to think about Fibonacci Numbers.
1. There are $n$ number of balls of only two colors (Let these be red and blue).
2. The red balls are identical and so are blue balls.
3. No two red balls can be together.

Case n=1 ball -- 2 ways.
Clearly there are two ways to do this. Either you have a red ball or a blue ball.
$\binom{1+1}{0}+\binom{1}{1}=1+1=2$

Case n=2 balls -- 3 ways.
BB (2 Blue)

BR (1 Blue 1 Red)
RB
$\binom{2+1}{0}+\binom{2}{1}=1+2=3$

Case n = 3 balls -- 5ways
BBB (3 blue)

BBR (2 Blue 1 Red)
BRB
RBB

RBR (1 Blue 2 Red)
$\binom{3+1}{0}+\binom{3}{1}+\binom{2}{2}=1+3+1=5$

Case n=k balls $\binom{k+1}{0}+\binom{k}{1}+\binom{k-1}{2}+\cdots$

In Summation notation $\sum_{i=0}^{k}\binom{n+1-i}{i}$

Note the reason for $k+1$ is because we are trying to find the number of space among $k$ blue balls and there are $k+1$ such space and we are trying to find $0$ spot for a red ball.

In second case we have $k-1$ blue balls and we have $k$ spots and we are trying to find one spot for the red balls. So we can generalize this for $k$ balls starting with all blue balls and they have $k+1$ space between them. However we need $0$ red balls to be placed. As total number of balls have to be $k$ In next case we have $k-1$ blue balls and there are $k$ space among these blue balls and we need $1$ space for our red ball and this can be done in $\binom{k-1+1}{1}= \binom{k}{1}$ After this we have $k-2$ blue balls and $2$ red balls. For $k-2$ blue balls we have $k-2+1= k-1$ spaces and two spaces for red balls can be chosen in $\binom{k-1}{2}$ and so on.