Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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
See also the answers to The answer should be $F_{n+1}$, not $F_n$. – robjohn Feb 7 '13 at 21:40

7 Answers 7

up vote 6 down vote accepted

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

share|cite|improve this answer
Just to assign proper credit, this book has two authors: Arthur T. Benjamin and Jennifer J. Quinn. – Byron Schmuland Feb 7 '13 at 19:53
Usually, $F_1=F_2=1$. – robjohn Feb 7 '13 at 21:44
Thanks! I hadn't noticed my off by 1. All fixed. – Sam DeHority Feb 7 '13 at 23:39

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

share|cite|improve this answer

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

share|cite|improve this answer
+1 Again Fibonacci calls here – Babak S. Feb 8 '13 at 17:40
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 you did above. :-) – Babak S. Feb 8 '13 at 18:37

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

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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