Probar

Question

Probar: $\binom{n}{0}F_0+\binom{n}{1}F_1+\binom{n}{2}F_2+\cdots+\binom{n}{n}F_n=F_{2n}$; Me pegué con esta pregunta por un tiempo... ¡Ayudame por favor!!!!!! ¡Gracias!!!!!!

Answer 1

Un recuento de argumento:

El número de formas de escalada $n$ escaleras, teniendo en $1$ o $2$ pasos a la vez es $F_n$ (Trate de probar).

Ahora supongamos que tenemos para subir a $2n$ escaleras. Tenga en cuenta que necesitamos tener al menos $n$ se mueve.

Ahora consideramos la posición después de tomar exactamente $n$ se mueve. Para cada posición, tenemos en cuenta dónde estamos y cómo muchas maneras en que podemos cubrir el resto.

Esto lo hacemos considerando el número de pasos de $2$ tomamos.

Si tomamos $k$$2$, entonces tomamos $n-k$ $1$ para el primer $n$ se mueve. Terminamos en el paso $n+k$, dejando $n-k$ pasos para cubrir. Estos $n-k$ pasos que pueden ser cubiertos en $F_{n-k}$ formas y el número de maneras de llegar allí es el mismo que el número de maneras de elegir a $k$ se mueve de $2$$n$,$\binom{n}{k}$.

Así como $k$ rangos de$0$$n$, tenemos que el número de maneras de cubrir $2n$ escaleras es

$$F_{2n} = \sum_{k=0}^{n} \binom{n}{k} F_{n-k}$$

Desde $\binom{n}{k} = \binom{n}{n-k}$ tenemos

$$ \binom{n}{0}F_0 + \binom{n}{1}F_1 + \dots + \binom{n}{n}F_n = F_{2n}$$

Una simple generalización de este argumento nos da, para $2n \le m$

$$ \binom{n}{0} F_{m-2n} + \binom{n}{1} F_{m-2n+1} + \dots + \binom{n}{n} F_{m-n} = F_m$$

Answer 2

Sugerencia: fórmula de Binet + fórmula Binomial. Además, $\varphi^2=\varphi+1$ y $\varphi^{-2}=2-\varphi$.

$$\hskip 1.5in \displaystyle \sum_{\ell=0}^n \binom{n}{\ell}\frac{\varphi^\ell-(1-\varphi)^\ell}{\sqrt5}=\frac{(1+\varphi)^{\ell}-(2-\varphi)^\ell}{\sqrt5}=F_{2n} $$

Answer 3

Accidentalmente, me topé con esta vieja pregunta, mientras que el estudio de algunos hechos acerca de la generación de funciones y no pudo resistirse a la publicación de esta respuesta. Tomar ordinaria de 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 \end{array}\right)F_kx^n$$ Cambiar el orden de la suma para obtener

$$G(x)=\sum_{k\ge0}\sum_{n\ge k}\left(\begin{array}{c} n\\ k \end{array}\right)F_kx^n=\sum_{k\ge0}F_k\sum_{n\ge0}\left(\begin{array}{c} n+k\\ k \end{array}\right)x^{n+k}\\=\sum_{k\ge0}F_kx^k\sum_{n\ge0}\left(\begin{array}{c} n+k\\ n \end{array}\right)x^n=\sum_{k\ge0}F_kx^k\frac{1}{\left(1-x\right)^{1+k}}\\=\frac{1}{1-x}\sum_{k\ge0}F_k\left(\frac{x}{1-x}\right)^k$$ Ahora la expresión bajo la suma es sólo el ordinario de la generación de $F(z)$función para $F_n$ $$F(z)=\frac{z}{1-z-z^2}$$ donde $z=\frac{x}{1-x}$. Sustituyendo obtenemos $$G(x)=\frac{x}{1-3x-x^2}$$ La última expresión es la generación de la función de $F_{2n}$ como puede ser comprobada mediante el cálculo de $\frac{1}{2}\left[F(x)+F(-x)\right]$