3

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?

TheSimpliFire
  • 26,246
  • 10
  • 58
  • 125
  • Possible duplicate of [Proof of the Hockey-Stick Identity: $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$](https://math.stackexchange.com/questions/1490794/proof-of-the-hockey-stick-identity-sum-limits-t-0n-binom-tk-binomn1) – Guy Fsone Dec 01 '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 01 '17 at 19:15
  • @JackD'Aurizio I got it thanks – Guy Fsone Dec 01 '17 at 19:19
  • 1
    See [The Fibonacci numbers occur in the sums of "shallow" diagonals in Pascal's triangle](https://en.wikipedia.org/wiki/Fibonacci_number#Use_in_mathematics). – Felix Marin Dec 01 '17 at 23:50

2 Answers2

5

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.

Jack D'Aurizio
  • 348,665
  • 41
  • 374
  • 814
1

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

Sil
  • 15,281
  • 3
  • 36
  • 75