# 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?

• – Guy Fsone Dec 1 '17 at 18:58
• @GuyFsone: the point here is not to prove the hockey stick (or stars and bars) identity, but to understand how it is related to Fibonacci numbers. – Jack D'Aurizio Dec 1 '17 at 19:15
• @JackD'Aurizio I got it thanks – Guy Fsone Dec 1 '17 at 19:19
• – Felix Marin Dec 1 '17 at 23:50

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.

• I don't really get the interpretation of $S_n$. Say we have the string $0101$. What does that mean? – TheSimpliFire Dec 1 '17 at 19:34
• @TheSimpliFire: $0101$ it is an element of $S_4$, associated with $k=2$ and $2+1+1$. – Jack D'Aurizio Dec 1 '17 at 19:40
• $S_4$ has $8$ elements, namely $$0000,0001,0010,0100,0101,1000,1001,1010$$ associated with $$6, 4+1,3+2,2+3,2+1+1,1+4,1+2+1,1+1+2.$$ – Jack D'Aurizio Dec 1 '17 at 19:45
• Thank you. But why is $0010$ associated with $3+2$? – TheSimpliFire Dec 1 '17 at 19:52
• @TheSimpliFire: add an initial and a final zero to get $000100\mapsto 3+2$. – Jack D'Aurizio Dec 1 '17 at 19:58

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

• clever use of summations and series! – TheSimpliFire Dec 2 '17 at 14:05