Demostrar la siguiente igualdad: $\sum_{k=0}^n\binom {n-k }{k} = F_n$

Question

Necesito demostrar que existe la siguiente igualdad:

$$ \sum\limits_{k=0}^n {k n \choose k} = F_ {n} $$ donde $F_{n}$ es un n-ésimo número de Fibonacci.

El problema parece fácil pero no encuentro la manera de demostrarlo. ¿Me podría dar alguna sugerencias? Estoy buscando una prueba combinatoria.

Answer 1

Aliniación

Answer 2

Inducción de triángulo de Pascal:

$$\begin{array}{c} \begin{array}{} \color{green}{\bullet}&+&\color{blue}{\bullet}\\ &&\parallel\\ &&\color{red}{\bullet} \end{matriz} & & &: & & &\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{matriz} \end{array}$$

Answer 3

Arthur Benjamin en realidad escribió un libro que me parecía ser nada distinto de propiedades combinatorias de Fibonacci y otros números similares, llamados "las Pruebas de que Realmente cuenta". Me pareció bastante interesante. $F_n$ tiene una representación popular como una combinatoria de objeto, y que es el número de secuencias de 1s y 2s que se suma a la forma $n-1$. Esto es $F_n$ porque $F_1 = F_2 = 1$ y el número de maneras de hacer $n-1$ es el número de secuencias que se suma a $n-3$ con un dos en la final, y el número de maneras en que la suma de a $n-2$ con un 1 al final. Esto puede ser refundida con un número de otras situaciones, como colorante de las secuencias de las baldosas o la colocación de fichas de dominó, pero es la misma idea.

Ahora esta identidad viene de contar el número de maneras para formar esta suma que contienen exactamente $k$ $2s$ en la secuencia. Sumando esta de $0$ $n$es lo mismo que sumar de a $0$ $[\frac{n}{2}]$y es encontrar cómo muchas secuencias con 1 de dos, 2 de dos en dos, y así sucesivamente. Esto termina siendo el número total de maneras de hacer la secuencia, a pesar de que viene a ser $F_{n+1}$ e no $F_n$, como la secuencia de Fibonacci es generalmente indexadas en $1$ e no $0$ (por lo tanto, ¿por qué estamos sumando a $n-1$).

Answer 4

Tome la generación de la función de la LHS:

$$G(x)=\sum_{n\ge0}\sum_{0\le k\le n}\left(\begin{array}{c} n-k\\ k \end{array}\right)x^n$$ Cambiar el orden de la suma de $$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}$$ La última expresión por la Regla 1, p34 es la generación de la función de $F_n$ dividido por $x$.

Answer 5

Para una prueba no combinatoria, la clave es la identidad de Fibonacci-como para los coeficientes binomiales, $$ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1} $$ entonces podemos calcular el % de la suma $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 {Alinee el} $$ haber hecho las bases, es bastante fácil de envolver una inducción prueba alrededor de esto, así que acredite su identidad.