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}$ 

Using the recursion for Pascal's Triangle, $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$, we get
$$
\begin{align}
a_n
&=\binom{n}{0}+\binom{n-1}{1}+\binom{n-2}{2}+\dots\\
&=\binom{n-1}{0}+\binom{n-2}{1}+\binom{n-3}{2}+\dots\\
&+\binom{n-1}{-1}+\binom{n-2}{0}+\binom{n-3}{1}+\dots\\[4pt]
&=a_{n-1}+a_{n-2}
\end{align}
$$
Noting that $a_0=1$ and $a_1=1$, we get $a_n=F_{n+1}$.

If there is concern over the term $\binom{n-1}{-1}$, consider the edge of Pascal's Triangle. Looking at it as $\binom{n}{0}=\binom{n-1}{0}+0$ and $\binom{n}{0}=\binom{n-1}{0}+\binom{n-1}{-1}$, we get $\binom{n-1}{-1}=0$. Furthermore, we have the identity $\binom{n-1}{k-1}=\frac kn\binom{n}{k}$. Set $k=0$ and we get $\binom{n-1}{-1}=0$. However we look at it, we get
$$
\binom{n-1}{-1}=0
$$
