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

Another way is using generating functions.  The g.f. of $\displaystyle a_n = \sum_{k=0}^{\lfloor n/2 \rfloor} {n-k \choose k} $ is
$$ \eqalign{G(x) & =\sum_{n=0}^\infty  \sum_{k=0}^{\lfloor n/2 \rfloor} {n-k \choose k} x^n\cr  &= \sum_{k=0}^\infty \sum_{n=2k}^\infty {n-k \choose k} x^n\cr
&= \sum_{k=0}^\infty x^{2k} \sum_{m=0}^\infty {m+k \choose k} x^m\cr
&= \sum_{k=0}^\infty \dfrac{x^{2k}}{(1-x)^{k+1}} \cr 
&= \dfrac{1}{1-x}\; \dfrac{1}{1 - x^2/(1-x)}\cr& = \dfrac{1}{1-x-x^2}}$$
The g.f. of the Fibonacci numbers $F_n$ is
$$ F(x) = \sum_{n=0}^\infty F_n x^n = \dfrac{x}{1+x-x^2} $$
with $F_0 = 0$, so the g.f. of $F_{n+1}$ is $F(x)/x = 1/(1+x-x^2) = G(x)$.
