Un amigo me mostró este truco: Tomar cualquier fila del triángulo de Pascal (es decir, $n = 7$): $$1, 7, 21, 35, 35, 21, 7, 1$$ Dejar fuera todos los otros números, comenzando con el primero: $$7, 35, 21, 1$$ A continuación, estos son hacia atrás base-5 "dígitos", así que calcular: $$7 + 35 \cdot 5 + 21 \cdot 5^2 + 1 \cdot 5^3 = 7 + 175 + 525 + 125 = 832$$ y dividir por $2^{7-1} = 2^6 = 64$: $$\frac{832}{64} = 13$$ y $F_7 = 13$ (el séptimo número Fibonacci)! Él dijo que trabaja para cualquier $n$. Yo me imagino que este será demostrar que: $$\frac{1}{2^{n-1}}\sum_{k = 0}^{\lfloor{\frac{n}{2}}\rfloor}{\left(5^k {n \choose 2k + 1} \right)} = F_n $$ No estoy seguro de cómo proceder a partir de aquí. Hay una casa combinatoric o fáciles de la prueba de álgebra me estoy perdiendo? Gracias!
Respuestas
¿Demasiados anuncios?
Fácil la prueba de álgebra. Sólo el uso de la fórmula de Binet: $$F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n \right) $$ Si expande los poderes mediante los coeficientes binomiales y simplificar, usted verá que los términos con $\sqrt{5}$ cancelar y usted debe obtener el resultado deseado exactamente!
Supongamos que tratamos de demostrar que
$$\frac{1}{2^{n-1}} \sum_{k=0}^{\lfloor n/2\rfloor} 5^k {n\elegir 2k+1} = F_n$$
un número Fibonacci. Introducir
$${n\elegir 2k+1} = {n\elegir n-2k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-2k}} (1+z)^n \; dz.$$
Observar que el mayor índice de $k$ producir un valor distinto de cero es $\lfloor n/2\rfloor-1$ al $n$ es incluso y $\lfloor n/2\rfloor$ cuando $n$ es impar. La integral representa correctamente este comportamiento. La ampliación de la gama de $k$ hasta el infinito, por lo tanto, para obtener la suma
$$\frac{1}{2^{n-1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} (1+z)^n \sum_{k\ge 0} 5^k z^{2k} \; dz \\ = \frac{1}{2^{n-1}} \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} (1+z)^n \frac{1}{1-5z^2} \; dz.$$
Ahora pon $z/(1+z) = w$, de modo que $z = w/(1-w)$ $dz = 1/(1-w)^2 dw$ para obtener
$$\frac{1}{2^{n-1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^n} \frac{1}{1-5w^2/(1-w)^2} \frac{1}{(1-w)^2} \; dw \\ = \frac{1}{2^{n-1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1}{w^n} \frac{1}{1-2w-4w^2} \; ps.$$
La extracción de los coeficientes encontramos
$$\frac{1}{2^{n-1}} [w^{n-1}] \frac{1}{1-2w-4w^2} = [w^{n-1}] \frac{1}{1-2(w/2)-4(w/2)^2} \\ = [w^{n-1}] \frac{1}{1-w-w^2} \\ = [w^{n}] \frac{w}{1-w-w^2}.$$
Este es, precisamente, la generación de la función de los números de Fibonacci y hemos terminado.
Comenzando con la Fórmula de Binet: $$F_n = \frac{1}{\sqrt{5}} \left( \left(\frac{1 + \sqrt{5}}{2} \right)^n - \left(\frac{1 - \sqrt{5}}{2} \right)^n \right) $$ Ampliar el uso de Fórmula Binominal: $$F_n = \frac{1}{2^n\sqrt{5}} \left( \sum_{k=0}^n \left({n \choose k} \left( \sqrt{5} \right)^k\right) - \sum_{k=0}^n \left({n \choose k} \left( \sqrt{5} \right)^k \left(-1\right)^k\right) \right) $$ Combinar: $$F_n = \frac{1}{2^n\sqrt{5}} \left( \sum_{k=0}^n \left({n \choose k} \left( \sqrt{5} \right)^k\left(1-\left(-1\right)^k\right)\right)\right) $$ Pero $1 - \left(-1\right)^k$ $0$ incluso $k$ $2$ por extraño $k$. Por lo que podemos considerar sólo el caso en que $k$ es impar, por lo $k = 2j + 1$: $$F_n = \frac{1}{2^n\sqrt{5}} \left( \sum_{2j+1=1}^{2j+1=n} \left({n \choose 2j+1} \left( \sqrt{5} \right)^{2j+1}\cdot2\right)\right) $$ Simplificar: $$F_n = \frac{1}{2^{n-1}\sqrt{5}} \sum_{j=0}^{\lfloor{\frac{n}{2}}\rfloor} \left({n \choose 2j+1} \left( 5^j \sqrt{5} \right)\right) $$ $$F_n = \frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor{\frac{n}{2}}\rfloor} \left(5^j {n \choose 2j+1} \right) $$ Y hemos terminado!!
Para cancelar los coeficientes binomiales, incluso con la parte inferior de los índices, la suma puede ser escrito como $$ \begin{align} \frac1{2^{n-1}}\sum_{k=0}^n\binom{n}{k}\frac{\sqrt5^k-\left(-\sqrt5\right)^k}{2\sqrt5} &=\frac{\left(\frac{1+\sqrt5}2\right)^n-\left(\frac{1-\sqrt5}2\right)^n}{\sqrt5}\\ &=F_n \end{align} $$
