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.