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

This question already has an answer here:

  • finding the combinatorial sum [duplicate]

    2 answers

Solutions Collecting From Web of "Prove the following equality: $\sum_{k=0}^n\binom {n-k }{k} = F_n$"

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

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

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

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

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.