Proof $\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$ where $f_n$ is the n-th Fibonacci-number

Question

In our combinatorics script it is written, that

$$\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$$ where $f_n$ is the n-th Fibonacci-number.

Apparently this can be proven through the generating function

$$A(x) = \sum_{n=0}^\infty x^n \sum_{k=0}^\infty \binom{k}{n-k}$$

I've looked on stackexchange math and on the internet, but I couldn't find a proof.

I know that $$\sum_{k\ge0} \binom{n-k}k=f_{n+1}$$

and it can be proven through this

$$\sum_{k\ge0} \binom{n+1-k}k=\sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-k}{k-1}= \sum_{k\ge0} \binom{n-k}k + \sum_{k\ge0} \binom{n-1-(k-1)}{k-1}= \sum_{k\ge0} \binom{n-k}k + \sum_{j\ge0} \binom{n-1-j}{j}= f_{n+1}+f_n = f_{n+2}.$$

But I don't know how its done for the first case.

Answer 1

\begin{align} A(x) &= \sum_{n\ge 0} x^n\sum_{k\ge 0} \binom{k}{n-k} \\&= \sum_{k\ge 0} \sum_{n\ge 0} \binom{k}{n-k}x^n \\&= \sum_{k\ge 0} x^k\sum_{n\ge k} \binom{k}{n-k}x^{n-k} \\&= \sum_{k\ge 0} x^k\sum_{n\ge 0} \binom{k}{n}x^{n} \\&= \sum_{k\ge 0} x^k(1+x)^k \\&= \frac1{1-(x+x^2)} \end{align} All that remains is to recall $\sum_{n\ge 0} f_nx^n=\frac{x}{1-x-x^2}$.

Answer 2

Both $\binom{k}{n - k}$ and $\binom{n - k}{k}$ are only non-zero if $0 \le k \le n$ (so the sums are finite). The sum $\sum_{k} \binom{n-k}k$ can be written as

$$ \binom{n}{0} + \binom{n - 1}{1} + \binom{n - 2}{2} + \cdots + \binom{n - n}{n}. $$

If you reverse the order (which corresponds to the involution $k \leftrightarrow n - k$), you get

$$ \binom{0}{n} + \binom{1}{n - 1} + \binom{2}{n-2} + \cdots + \binom{n}{n-n},$$

which is the sum $\sum_k \binom{k}{n-k}$.