# Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$ [duplicate]

I need to prove that there is the following equality:

$$\sum\limits_{k=0}^n {n-k \choose k} = F_{n}$$ where $F_{n}$ is a n-th Fibonacci number.

The problem seems easy but I can't find the way to prove it. Could you give me any hints? I'm looking for a combinatorial proof.

## marked as duplicate by Marc van Leeuwen, Sasha, Asaf Karagila♦, Davide Giraudo, JSchlatherFeb 23 '13 at 18:34

• You'll need a combinatorial definition for $F_n$ to come up with a combinatorial proof. – Thomas Andrews Feb 7 '13 at 19:31
• Why not try proving that the LHS satisfies $s_{n+1}=s_n+s_{n-1}$ with $s_0=1$, $s_1=1$ – Pedro Tamaroff Feb 7 '13 at 19:31
• It does seem like induction would be the most direct approach. – Thomas Andrews Feb 7 '13 at 19:32
• – user940 Feb 7 '13 at 19:37
• See also the answers to math.stackexchange.com/q/292940. The answer should be $F_{n+1}$, not $F_n$. – robjohn Feb 7 '13 at 21:40

Arthur Benjamin actuall wrote a book that seemed to me to be nothing other than combinatorial properties of Fibonacci and other similar numbers, called "Proofs that Really Count". I found it rather interesting. $F_n$ has one popular representation as a combinatorial object, and that is the number of sequences of 1s and 2s that sum to form $n-1$. This is $F_n$ because $F_1 = F_2 = 1$ and the number of ways to make $n-1$ is the number of sequences that sum to $n-3$ with a two at the end, and the number of ways to sum to $n-2$ with a 1 at the end. This can be recast with a number of other situations, like coloring sequences of tiles or placing dominoes, but it's the same idea.

Now this identity comes from counting the number of ways to form this sum that contain exactly $k$ $2s$ in the sequence. Summing this from $0$ to $n$ is the same as summing from $0$ to $[\frac{n}{2}]$ and is finding how many sequences with 1 two, 2 twos, and so on. This ends up being the total number of ways to make the sequence, although it comes out to be $F_{n+1}$ and not $F_n$, as the Fibonacci sequence is usually indexed at $1$ and not $0$ (hence why we are summing to $n-1$).

• Just to assign proper credit, this book has two authors: Arthur T. Benjamin and Jennifer J. Quinn. – user940 Feb 7 '13 at 19:53
• Usually, $F_1=F_2=1$. – robjohn Feb 7 '13 at 21:44

\begin{align} F_n&=\sum_{k=0}^n\binom{n-k}{k}\\ &=\sum_{k=0}^{n}\Bigg(\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\Bigg)\\ &=\sum_{k=0}^{n-1}\Bigg(\binom{(n-1)-k}{k}+\binom{n-2-(k-1)}{(k-1)}\Bigg)\\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{k=0}^{n-1}\binom{n-2-(k-1)}{k-1}\\ &=\sum_{k=0}^{n-1}\binom{(n-1)-k}{k}+\sum_{j=0}^{n-2}\binom{(n-2)-j}{j}\\ &=F_{n-1}+F_{n-2} \end{align}

• Yes Babak that is one of my favorite sequences – Adi Dani Feb 8 '13 at 18:34
• You know, whenever I am faced to these kinds of problems; I leave them. Becuse I cannot type in Latex many parentheses and ...like you did above. :-) – mrs Feb 8 '13 at 18:37

The Pascal’s triangle induction:

$$\begin{array}{c} \begin{array}{} \color{green}{\bullet}&+&\color{blue}{\bullet}\\ &&\parallel\\ &&\color{red}{\bullet} \end{array}&&&:&&& \begin{array}{r} (0)&1\\ (0)&1&1&&&&\color{green}{F_7}&\color{blue}{F_8}&\color{red}{F_9}\\ (0)&1&2&1&&\color{green}{\nearrow}&\color{blue}{\nearrow}&\color{red}{\nearrow}\\ (0)&1&3&3&\color{green}{1}&\color{blue}{(0)}&\color{red}{\nearrow}\\ (0)&1&4&\color{green}{6}&\color{blue}{4}&\color{red}{1}\\ (0)&1&\color{green}{5}&\color{blue}{10}&\color{red}{10}&5&1\\ (0)&\color{green}{1}&\color{blue}{6}&\color{red}{15}&20&15&6&1\\ \color{green}{(0)}&\color{blue}{1}&\color{red}{7}&21&35&35&21&7&1\\ (0)&\color{red}{1}&8&28&56&70&56&28&8&1 \end{array} \end{array}$$

Take the generating function of the LHS:

$$G(x)=\sum_{n\ge0}\sum_{0\le k\le n}\left(\begin{array}{c} n-k\\ k \end{array}\right)x^n$$ Change the order of summation $$G(x)=\sum_{k\ge0}\sum_{n\ge k}\left(\begin{array}{c} n-k\\ k \end{array}\right)x^n=\sum_{k\ge0}x^k\sum_{n\ge 0}\left(\begin{array}{c} n\\ k \end{array}\right)x^n\\=\sum_{k\ge 0}x^k\frac{x^k}{\left(1-x\right)^{k+1}}=\frac{1}{1-x}\sum_{k\ge0}\left(\frac{x^2}{1-x}\right)^k\\=\frac{1}{1-x}\frac{1-x}{1-x-x^2}=\frac{1}{1-x-x^2}$$ The last expression by Rule 1, p34 is the generating function of $F_n$ divided by $x$.

• The generating function for $F_n$ divided by $x$ is the generating function for $F_{n+1}$ since $F_0=0$ (which is what I say in my answer). – robjohn Feb 8 '13 at 18:17

For a non-combinatorial proof, the key is the Fibonacci-like identity for binomial coefficients, $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$$ Then we can compute the sum $F_{n-1}+F_{n-2}$:

\begin{align} F_{n-1}+F_{n-2} &= \sum_{k=0}^{n-1}\binom{n-1-k}{k}+\sum_{k=0}^{n-2}\binom{n-2-k}{k}\\ &= \binom{n-1}{0}+\sum_{k=1}^{n-1}\left[\binom{n-k-1}{k}+\binom{n-k-1}{k-1}\right]\\ &= \binom{n}{0}+\sum_{k=1}^{n-1}\binom{n-k}{k}\\ &= \sum_{k=0}^n\binom{n-k}{k} \end{align} Having done the groundwork, it's easy enough to wrap an induction proof around this, thus proving your identity.

This is a duplicate answer, since this is essentially a duplicate question.

Another approach is to look at the generating function \begin{align} \sum_n\sum_k\binom{n-k}{k}x^n &=\sum_n\sum_k\binom{n}{k}x^{n+k}\\ &=\sum_nx^n(1+x)^n\\ &=\frac1{1-x-x^2}\\ &=\frac1{\sqrt5}\left(\frac{\phi}{1-\phi x}+\frac{1/\phi}{1+x/\phi}\right)\\ &=\sum_n\frac{\phi^{n+1}-(-1/\phi)^{n+1}}{\sqrt5}x^n \end{align} Thus, \begin{align} \sum_k\binom{n-k}{k} &=\frac{\phi^{n+1}-(-1/\phi)^{n+1}}{\sqrt5}\\ &=F_{n+1} \end{align} where $F_n$ is the $n^{\text{th}}$ Fibonacci number.

The sequences $F_{n}$ and $G_n=\sum_{i+j = n} {i \choose j}$ have the same initial conditions:

$$G_0 = \binom{0}{0}=0=F_0, G_1 = \binom{1}{0}+\binom{0}{1} = 1 = F_1$$

And they satisfy the same order-2 recursion:

$$G_{n+2} = \sum_{i+j = n+2} {i \choose j} = \sum_{i+j = n+2} ({i-1 \choose j}+{i-1 \choose j-1})=$$ $$\sum_{(i-1)+j = n+1} {i-1 \choose j} + \sum_{(i-1)+(j-1) = n} {i-1 \choose j-1}=G_n + G_{n+1}$$

Hence those 2 sequences coincide.