Proving that $\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\cdots =F_{n+1}$ where $F_{n+1}$ is the $n+1$ th Fibonacci number I have to proove this this identity which connects Fibonacci sequence and Pascal's triangle:
$$\begin{pmatrix}n\\0\end{pmatrix}+\begin{pmatrix}n-1\\1\end{pmatrix}+\dotsm+\begin{pmatrix}n-\lfloor\frac{n}{2}\rfloor\\\lfloor\frac{n}{2}\rfloor\end{pmatrix} = F_{(n+1)}$$
Example: ${6\choose0} + {5\choose1} + {4\choose2} + {3\choose3} = 13 = F_{7}$ 

Use induction and a little cheat!
Consider $F_5=\dbinom50+\dbinom41+\dbinom32=1+4+3=8$
Now $\dbinom{n}{k-1}+\dbinom{n}{k}=\dbinom{n+1}{k}$, so for example $\dbinom41+\dbinom42=\dbinom52$.
So adding these like terms gives us the next Fibonacci number, except for the misplaced leading term.
And we have $\dbinom{n}{0}=1$ for all $n\in\mathbb{N}$ so we shift the leading term outwards, which is a bit like cheating really!
There's loads of pictures at Google.
