Prueba$\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$ donde$f_n$ es el n-ésimo número de Fibonacci

Question

En nuestro combinatoria guión está escrito, que

$$\sum_{k=0}^\infty \binom{k}{n-k} = f_{n+1}$$ where $f_n$ es el n-ésimo de Fibonacci-número.

Al parecer, esto puede ser demostrado a través de la generación de la función

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

He mirado en stackexchange matemáticas y en internet, pero no pude encontrar una prueba.

Sé que $$\sum_{k\ge0} \binom{n-k}k=f_{n+1}$$

y puede ser probada a través de este

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

Pero no sé cómo se realizan para el primer caso.

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} Todo lo que queda es recuperar $\sum_{n\ge 0} f_nx^n=\frac{x}{1-x-x^2}$ .

Answer 2

Ambos $\binom{k}{n - k}$ e $\binom{n - k}{k}$ son sólo los no-cero si $0 \le k \le n$ (de modo que las sumas son finitos). La suma de $\sum_{k} \binom{n-k}k$ puede ser escrito como

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

Si se invierte el orden (que corresponde a la involución $k \leftrightarrow n - k$), se obtiene

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

que es la suma de $\sum_k \binom{k}{n-k}$.