<s>[INST] Is it true that $\sum_{k=0}^m\binom{n-k}k$ outputs the $(n+1)$th Fibonacci number, where $m=\frac{n-1}2$ for odd $n$ and $m=\frac n2$ for even $n$? 
Does $$\sum_{k=0}^m\binom{n-k}k=F_{n+1}$$ where $m=\left\{\begin{matrix}
\frac{n-1}{2}, \text{for odd} \,n\\ 
\frac n2, \text{for even} \,n
\end{matrix}\right.$ hold for all positive integers $n$?

Attempt:
I have not yet found a counterexample, so I will attempt to prove it.
$$\text{LHS} =\binom n0 + \binom{n-1}1+\binom{n-2}2+...+\left\{\begin{matrix}
\binom{1+(n-1)/2}{(n-1)/2}, \text{for odd} \,n\\ 
\binom{n/2}{n/2}, \text{for even} \,n
\end{matrix}\right.$$
Now using the identity that $\binom nk + \binom n{k+1}=\binom {n+1}{k+1}$, where $k$ is a positive integer, I find that $$\binom{n-1}1=\binom n1 - 1, \\ \binom {n-2}2=\binom n2-2\binom n1+3,\\ \binom {n-3}{3} =\binom n3 - 3\binom n2 + 6 \binom n1 - 10, \\ ...$$ This pattern suggests that the coefficients of $\binom{n-4}4$ will be square numbers, those of $\binom{n-5}5$ will be pentagonal numbers, etc. However, I cannot see a way to link these results to any Fibonacci identity. 
Edit: @Jack D'Aurizio♢ has provided a very succinct proof to this, but is there a more algebraic method to show the equality? 
 [/INST] Here is more of an algebraic solution through generating functions. We have
\begin{align}
\sum_{n=0}^{\infty}\sum_{k=0}^{\lfloor n/2\rfloor}\binom{n-k}{k}x^n
&=\sum_{k=0}^{\infty}\sum_{n=k}^{\infty}\binom{n}{k}x^{n+k+1}\\
&=\sum_{k=0}^{\infty}x^{2k+1}\sum_{n=k}^{\infty}\binom{n}{k}x^{n-k}\\
&=\sum_{k=0}^{\infty}x^{2k+1}\sum_{n=0}^{\infty}\binom{n+k}{k}x^{n}\\
&=\sum_{k=0}^{\infty}x^{2k+1}\frac{1}{(1-x)^{k+1}}\\
&=\frac{x}{1-x}\sum_{k=0}^{\infty}\left(\frac{x^2}{1-x}\right)^k\\
&=\frac{x}{1-x}\frac{1}{1-\frac{x^2}{1-x}}\\
&=\frac{x}{1-x-x^2}
\end{align}
where on the last line we arrived at the well known generating function for fibonacci numbers. So by equality of coefficients it follows
$$F_{n+1} = \sum_{k=0}^{\lfloor (n)/2\rfloor}\binom{n-k}{k}.$$
</s>