Fibonacci Numbers Proof: $ f_n = \binom n0 + \binom{n-1}1 +\dots+ \binom{n-k}k$
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} $$
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$.