9
$\begingroup$

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.

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

7 Answers 7

10
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Yes Babak that is one of my favorite sequences $\endgroup$
    – Adi Dani
    Feb 8, 2013 at 18:34
  • 1
    $\begingroup$ 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. :-) $\endgroup$
    – Mikasa
    Feb 8, 2013 at 18:37
7
$\begingroup$

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

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

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – robjohn
    Feb 8, 2013 at 18:17
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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