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?


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.

| cite | improve this answer | |
  • $\begingroup$ I don't really get the interpretation of $S_n$. Say we have the string $0101$. What does that mean? $\endgroup$ – TheSimpliFire Dec 1 '17 at 19:34
  • $\begingroup$ @TheSimpliFire: $0101$ it is an element of $S_4$, associated with $k=2$ and $2+1+1$. $\endgroup$ – Jack D'Aurizio Dec 1 '17 at 19:40
  • $\begingroup$ $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.$$ $\endgroup$ – Jack D'Aurizio Dec 1 '17 at 19:45
  • $\begingroup$ Thank you. But why is $0010$ associated with $3+2$? $\endgroup$ – TheSimpliFire Dec 1 '17 at 19:52
  • $\begingroup$ @TheSimpliFire: add an initial and a final zero to get $000100\mapsto 3+2$. $\endgroup$ – 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}.$$

| cite | improve this answer | |
  • $\begingroup$ clever use of summations and series! $\endgroup$ – TheSimpliFire Dec 2 '17 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.