Fib. sequences/ Combintorics

Question

Can someone please help me prove the following: $\sum_{k=0}^{2n}{2n-k\choose k}=F_{n+1}$. I already know that $\sum_{k=0}^{n}{n+k\choose 2k}=F_{n+1}$, but I don't know how to prove $\sum_{k=0}^{n}{n+k\choose 2k}=\sum_{k=0}^{2n}{2n-k\choose k}=F_{n+1}$

Answer 1

I'll play and see what happens.

You want to show that $\sum_{k=0}^{2n}{2n-k\choose k}=F_{n+1} $.

First of all, if $k > n$ then $k > 2n-k$. Therefore $\sum_{k=0}^{2n}{2n-k\choose k} =\sum_{k=0}^{n}{2n-k\choose k} $.

Next,

$\begin{array}\\ \sum_{k=0}^{n}{2n-k\choose k} &=\sum_{k=0}^{n}{2n-k\choose (2n-k)-k} \qquad\binom{a}{b} = \binom{a}{a-b}\\ &=\sum_{k=0}^{n}{2n-k\choose 2n-2k}\\ &=\sum_{k=0}^{n}{2n-(n-k)\choose 2n-2(n-k)} \qquad\text{Reverse order of summation: } k \to n-k\\ &=\sum_{k=0}^{n}{n+k\choose 2k}\\ \end{array} $

and since you know that $\sum_{k=0}^{n}{n+k\choose 2k}=F_{n+1} $ we are done.

Note that this shows that $\sum_{k=0}^{n}{n+k\choose 2k} =\sum_{k=0}^{2n}{2n-k\choose k} $ without any evaluation of what the sums actually are.

Answer 2

I am going to assume that the Fibonacci number $F_n$ is defined as the $n$-th term of the sequence such that $F_0=0,F_1=1$, $F_{n+2}=F_{n+1}+F_n$.

Lemma. The number of strings over $\Sigma=\{0,1\}$ with length $m$ and no adjacent $1$s is $F_{m+2}$.

Proof. A valid string either starts with a $0$ followed by a valid string with $m-1$ characters, or with $10$ followed by a valid string with $m-2$ characters. Induction finishes the proof.

Observation. We may count the valid strings, according to their number of $1$s, through stars and bars. Let $m=2n-1$. If we have $k$ characters $1$, we have $2n-1-k$ characters zero, and a valid string with $k$ characters $1$ can be constructed by inserting them in the spaces between $2n-1-k$ consecutive zeroes, at the end or at the beginning, i.e. in $2n-k$ positions. It follows that $$ \sum_{k=0}^{n}\binom{2n-k}{k} = F_{\color{red}{2n+1}}.$$