Fibonacci Numbers Proof: $ f_n = \binom n0 + \binom{n-1}1 +\dots+ \binom{n-k}k$ Prove the following fibonacci sequence, which appear in Pascal's Triangle. I am not sure where to start on this, any pointers?
$$ f_n = {n\choose0} + {n-1\choose1} + ... + {n-k\choose k}$$
where $\displaystyle k=\left\lfloor\frac{n}{2}\right\rfloor$
 A: The proof is simpler if you include terms where the lower argument is greater than the upper argument: that is,
$$
F_{n+1}=\sum_{k=0}^{n}\binom{n-k}{k}\tag{1}
$$
The terms where $n-k\lt k$ are $0$.
Initial Values:
For $n=0$, the sum gives $1$.
For $n=1$, the sum gives $1$.
Recursion:
The recursion is satisfied:
$$
\begin{align}
\hspace{-1cm}\sum_{k=0}^{n}\binom{n-k}{k}+\sum_{k=0}^{n+1}\binom{n+1-k}{k}
&=\sum_{k=1}^{n+1}\binom{n+1-k}{k-1}+\sum_{k=0}^{n+1}\binom{n+1-k}{k}\tag{2}\\
&=1+\sum_{k=1}^{n+1}\binom{n+2-k}{k}\tag{3}\\
&=\sum_{k=0}^{n+2}\binom{n+2-k}{k}\tag{4}
\end{align}
$$
Explanation:
$(2)$: reindex the left sum $k\mapsto k-1$
$(3)$: pull out the $k=0$ term from the right sum and use $\binom{n+1}{k}=\binom{n\vphantom{1}}{k}+\binom{n\vphantom{1}}{k-1}$
$(4)$: put back the $k=0$ term
Note, however, that because of the initial values, the sum is actually $F_{n+1}$, and not $F_n$.
A: A combinatorial proof.
Fibonacci numbers count the number of ways to walk up $n$ steps, going one or two steps at a time.
$\binom{n-k}{k}$ counts the number of ways of walking up $n$ steps, going one or two steps at a time, but doing exactly $k$ two-steps.
(There are $n-2k$ one-steps, for a total of $n-k$ steps, of which you choose $k$ to be the two-steps)
A: Hint: Try to use induction and:
$$
\begin{align}
\tag{i}       f_{n+2} &= f_{n+1} + f_n \\
\tag{ii} \binom{n}{k} &= \binom{n-1}{k} + \binom{n-1}{k-1}
                         \qquad \text{for $n > 0$}
\end{align}
$$
