Let $F_m$ be the $mth$ Fibonacci number given by $F_1=F_2=1$ and $F_{m+2}=F_m+F_{m+1}$ for all $m\geq 1.$ Show that $\sum\binom nk=F_{m+1},$

Question

Let $\binom{n}{k}$ denote the binomial coefficient $\frac{n!}{k!(n-k)!}$ and $F_m$ be the $mth$ Fibonacci number given by $F_1=F_2=1$ and $F_{m+2}=F_m+F_{m+1}$ for all $m\geq 1.$ Show that $\sum\binom nk=F_{m+1},$ $\forall m\geq 1.$ Here, the above sum is over all pairs of integers $n\geq k\geq 0,$ with $n+k=m.$

My solution goes like this:

We see that $\sum\binom nk=F_{m+1},$ $\forall m\geq 1,$ is valid, for $m=1.$ Now, assuming $\sum\binom nk=F_{m+1},$ is true. It is to be noted, $n\geq k\geq 0,$ with $n+k=m.$ This, means, $n=m-k$ and $$n\geq k\implies m\geq 2k\implies k\leq \frac m2.$$

We observe, if $$k=0,1,2,\cdots, \lfloor \frac m2\rfloor$$, $$n=m,m-1,m-2,\cdots,m-\lfloor \frac m2\rfloor$$, respectively. $$\sum\binom nk=\binom{m}{0}+\binom{m-1}{1}+\binom{m-2}{2}+\cdots +\binom{m-\lfloor \frac m2\rfloor}{\lfloor \frac m2\rfloor}=F_{m+1}.$$

Now, we try to represent $\sum\binom nk=F_{m},$ , such that $n\geq k\geq 0,$ with $n+k=m-1,$ in the same form as above. This, means, $n=m-k-1$ and $$n\geq k\implies m-1\geq 2k\implies k\leq \frac {m-1}{2}.$$

We again observe, if $$k=0,1,2,\cdots, \lfloor \frac {m-1}{2}\rfloor$$, $$n=m-1,m-2,\cdots,m-\lfloor \frac {m-1}{2}\rfloor-1.$$ So, $$\sum\binom nk=\binom{m-1}{0}+\binom{m-2}{1}+\cdots +\binom{m-1-\lfloor \frac {m-1}{2}\rfloor}{\lfloor \frac {m-1}{2}\rfloor}=F_{m}.$$

Now, for $m+1$ we should have, $\sum\binom nk=F_{m+1},$ such that $n\geq k\geq 0,$ with $n+k=m+1.$ Also, if $n\geq k$, then, $m+1\geq 2k\implies k\leq \frac {m+1}{2}.$

We observe, if $$k=0,1,2,\cdots, \lfloor \frac {m+1}{2}\rfloor$$, $$n=m+1,m,\cdots,m-\lfloor \frac {m+1}{2}\rfloor+1.$$ So, $$\sum\binom nk=\binom{m+1}{0}+\binom{m}{1}+\binom{m-1}{2}+\cdots +\binom{m+1-\lfloor \frac {m+1}{2}\rfloor}{\lfloor \frac {m+1}{2}\rfloor}=F_{m+2}.$$

Now, we compute, $$F_{m+1}+F_m=(\binom{m}{0}+\binom{m-1}{1}+\binom{m-2}{2}+\cdots +\binom{m-\lfloor \frac m2\rfloor}{\lfloor \frac m2\rfloor})+(\binom{m-1}{0}+\binom{m-2}{1}+\cdots +\binom{m-1-\lfloor \frac {m-1}{2}\rfloor}{\lfloor \frac {m-1}{2}\rfloor})\implies \binom{m}{0}+(\binom{m-1}{1}+\binom{m-1}{0})+(\binom{m-2}{2}+\binom{m-2}{1})+\cdots +(\binom{m-\lfloor \frac m2\rfloor}{\lfloor \frac m2\rfloor} +\binom{m-1-\lfloor \frac {m-1}{2}\rfloor}{\lfloor \frac {m-1}{2}\rfloor}).$$ Using, Pascal's identity and the idenitity: $\lfloor\frac m2\rfloor=\lfloor\frac{m-1}{2}\rfloor +1,$ we have, $$F_{m+1}+F_m=\binom m0+\binom{m}{1}+\binom{m-1}{2}+\cdots+(\binom{m-\lfloor \frac m2\rfloor}{\lfloor \frac m2\rfloor} +\binom{m-\lfloor \frac {m}{2}\rfloor}{\lfloor \frac {m}{2}\rfloor-1})=\binom {m+1}{0}+\binom{m}{1}+\binom{m-1}{2}+\cdots+\binom{m-\lfloor \frac m2\rfloor+1}{\lfloor \frac m2\rfloor}.$$

Now, the problem is, in the expression $$F_{m+1}+F_m$$, every term matches with $$F_{m+2}$$ except the last term, $$\binom{m-\lfloor \frac m2\rfloor+1}{\lfloor \frac m2\rfloor}$$, which should be equivalent to, $\binom{m+1-\lfloor \frac {m+1}{2}\rfloor}{\lfloor \frac {m+1}{2}\rfloor}$ ? I don't get where is the problem occuring?

Answer 1

I think the error is in your matching of the terms in $F_{m+1}+F_m$: the pattern with one term of $F_{m+1}$, then pairs of terms, is correct for $m$ even, but for $m$ odd, there are the same number of terms in each sum, so there is a spare term at the end from $F_m$: that is, the final pair is $${m-\lfloor\frac{m}{2}\rfloor \choose \lfloor\frac{m}{2}\rfloor} +{m-1-\lfloor\frac{m-1}{2}\rfloor \choose \lfloor\frac{m-1}{2}\rfloor},$$ as you have, when $m$ is even, but when $m$ is odd, the final pair is $${m-\lfloor\frac{m}{2}\rfloor \choose \lfloor\frac{m}{2}\rfloor} +{m-\lfloor\frac{m-1}{2}\rfloor \choose \lfloor\frac{m-1}{2}\rfloor -1},$$ and there is an extra term of $${m-1-\lfloor\frac{m-1}{2}\rfloor \choose \lfloor\frac{m-1}{2}\rfloor},$$ which is equal to $1$ when $m$ is odd, and is just what you need to get the final sum as you want it.

Answer 2

One mistake you made is when you said $\lfloor\frac m2\rfloor=\lfloor\frac{m-1}{2}\rfloor +1$. This is only true when $m$ is even.

I find it is much easier to split into cases based on whether $m$ is even or odd.

If $m$ is even, so that $m=2k$ for some $k\in \mathbb N$, then $$ \begin{align} F_{m+2} &=F_m+F_{m+1}\\ &=\left[\binom{2k}0+\binom{2k-1}1+\dots+\binom{k}{k}\right]+\\ &\phantom{=}\left[\binom{2k+1}0+\binom{2k}1+\dots+\binom{k+1}{k}\right]\\ &=\binom{2k+1}0+\left[\binom{2k}{0}+\binom{2k}1\right]+\dots+\left[\binom{k+1}{k-1}+\binom{k+1}{k}\right]+\color{red}{\binom{k}k}\\ &=\binom{2k+2}0+\binom{2k+1}1+\dots+\binom{k+2}{k}+\color{red}{\binom{k+1}{k+1}} \end{align} $$

You need a different argument when $m$ is odd. Say $m=2k+1$ for some $k\in \mathbb N$. Then $$ \begin{align} F_{m+2} &=F_m+F_{m+1}\\ &=\left[\binom{2k+1}0+\binom{2k}1+\dots+\binom{k+1}{k}\right]+\\ &\phantom{=}\left[\binom{2k+2}0+\binom{2k+1}1+\dots+\binom{k+2}{k}+\binom{k+1}{k+1}\right]\\ &=\binom{2k+2}0+\left[\binom{2k+1}{0}+\binom{2k+1}1\right]+\dots+\left[\binom{k+1}{k}+\binom{k+1}{k+1}\right]\\ &=\binom{2k+3}0+\binom{2k+2}1+\dots+\binom{k+2}{k+1}\\ \end{align} $$ Notice the difference between the two arguments depending on the parity of $m$. When $m$ is odd, the last two terms in $F_m$ and $F_{m+1}$ combine together to make the last term of $F_{m+2}$. However, when $m$ is even, there is an extra $\color{red}{\text{red}}$ term in $F_m$, which becomes the last term of $F_{m+2}$. Instead, the second-to-last term of $F_{m+2}$ is made by combining the last term of $F_{m+1}$ with the second-to-last term of $F_m$.

This is why it is important to write out examples before plunging head first into the algebra! It is very hard to see looking at your formulas with floor functions the subtle difference between the required method of attack when $m$ is even versus odd, but this immediately becomes clear when your write out the proposed proof in small cases where $m$ is both even and odd, say $m=3$ and $m=4$.