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? 
 A: There is a simple combinatorial interpretation. Let $S_n$ be the set of strings over the alphabet $\Sigma=\{0,1\}$ with length $n$ and no occurrence of the substring $11$. Let $L_n=|S_n|$. We clearly have $L_1=2$ and $L_2=3$, and $L_n=F_{n+2}$ is straightforward to prove by induction, since every element of $S_n$, for $n\geq 3$, is either $0\text{(element of }S_{n-1})$ or $10\text{(element of }S_{n-2})$, so $L_{n+2}=L_{n+1}+L_n$.
On the other hand, we may consider the elements of $S_n$ with exactly $k$ characters $1$.
There are as many elements with such structure as ways of writing $n+2-k$ as the  sum of $k+1$ positive natural numbers. Here it is an example for $n=8$ and $k=3$:
$$ 00101001\mapsto \color{grey}{0}00101001\color{grey}{0}\mapsto \color{red}{000}1\color{red}{0}1\color{red}{00}1\color{red}{0}\mapsto3+1+2+1.$$
By stars and bars it follows that:
$$ L_n = F_{n+2} = \sum_{k=0}^{n}[x^{n+2-k}]\left(\frac{x}{1-x}\right)^{k+1}=\sum_{k=0}^{n}\binom{n+1-k}{k} $$
and by reindexing we get $F_{n+1}=\sum_{k=0}^{n}\binom{n-k}{k}$ as wanted.
A: 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}.$$
