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

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