7 votos

Contando el argumento prueba o prueba inductiva de $F_1 C^n_1+...+F_n C^n_n = F_{2n}$ $F_i$ dónde están Fibonacci

Demostrar que $$F_1 C^n_1+...+F_n C^n_n = F_{2n}$$ donde $C^n_k$ $n$ elija $k$ $F_i$ $i$ésimo número de Fibonacci.

Esta pregunta se menciona en Putnam y más Allá de libro número 861. Miré a la prueba de la pregunta, y el libro de la prueba utiliza la fórmula de Binet (es decir, la fórmula explícita para $n$ésimo número de Fibonacci), fórmula binominal, y el hecho de que $\frac{3+\sqrt{5}}{2} = (\frac{1+\sqrt{5}}{2})^2$. Me pregunto si hay un recuento de argumento para esta prueba (inductivo o de prueba), y si es así, sería genial si alguien publica aquí.

5voto

Micah Puntos 18257

(La siguiente respuesta es esencialmente Ejemplo 3.1.5 en este pdf.)

En primer lugar, $F_{2n}$ cuenta el número de formas de colocación de una tira de longitud $(2n-1)$ con azulejos de la longitud de cualquiera de las $1$ (cuadrados) o $2$ (dominó).

Ahora, veamos el número de mosaicos de esa franja en la que $k$ de la primera $n$ azulejos son cuadrados. Hay $\binom{n}{k}$ maneras de organizar la primera $n$ azulejos. Una colección de $k$ plazas y $n-k$ dominos tendrá la longitud de la $2n-k$. Así que la tira restante después de la primera $n$ baldosas tiene una longitud de $k-1$, lo que significa que puede ser acomodada en $F_k$ maneras. En resumen, el número de mosaicos de este tipo es $F_k \binom{n}{k}$.

Además, cualquier suelo de baldosas de la tira de usa, al menos, $n$ azulejos (o habría longitud en la mayoría de las $2n-2$), y la primera $n$ azulejos no pueden ser fichas de dominó (o habría longitud de $2n$). Así tenemos $$ F_{2n}=\sum_{k=1}^n F_n \binom{n}{k} $$ como se desee.

2voto

Joe Gauterin Puntos 9526

Esta es una manera de atacar el problema de la inducción. Tenemos que generalizar la declaración de un poco antes de que podamos llevar a cabo la inducción paso.

Ampliar la definición de $F_n$$F_0 = 0$. Para cualquier $n > 0$, vamos a $\mathcal{S}_n$ la declaración:

$$\mathcal{S}_n :\quad F_{2n+k} = \sum_{\ell=0}^n \binom{n}{\ell} F_{\ell+k},\;\text{ for all k} \ge 0$$ Cuando $n = 1$, $S_n$ se reduce a $F_{k+2} = F_{k+1} + F_k$ todos los $k \ge 0$. Esto es trivialmente cierto.

Suponga $\mathcal{S}_{n}$ es cierto. Para cualquier $k \ge 0$, tenemos

$$\begin{align}F_{2(n+1)+k} = F_{2n+(k+2)} &\stackrel{\mathcal{S}_n}{=} \sum_{\ell=0}^n \binom{n}{\ell} F_{\ell+(k+2)} = \sum_{\ell=0}^n \binom{n}{\ell} \left( F_{\ell+k+1} + F_{\ell+k}\right)\\ &= \sum_{\ell=1}^{n+1}\binom{n}{\ell-1}F_{\ell+k} + \sum_{\ell=0}^n \binom{n}{\ell} F_{\ell+k}\\ &= F_{n+1+k} + F_k + \sum_{\ell=1}^n \left(\binom{n}{\ell-1}+\binom{n}{\ell}\right)F_{\ell+k} \end{align} $$ Aviso de $\binom{n+1}{\ell} = \binom{n}{\ell}+\binom{n}{\ell-1}$$1 \le \ell \le n$, esto lleva a la $$F_{2(n+1)+k} = F_{n+1+k} + F_{k} + \sum_{\ell=1}^n \binom{n+1}{\ell}F_{\ell+k} = \sum_{\ell=0}^{n+1} \binom{n+1}{\ell}F_{\ell+k}$$ Ya que esto es válido para todos los $k$, $\mathcal{S}_{n+1}$ es cierto. Por el principio de inducción $\mathcal{S}_n$ es cierto para todos los $n$.
En particular, si corregimos $k$$0$, el deseo de identidad de la siguiente manera: $$F_{2n} = \sum_{\ell=0}^n \binom{n}{\ell}F_{\ell} = \sum_{\ell=1}^n \binom{n}{\ell}F_{\ell}$$

1voto

Amin235 Puntos 308

Aunque este no es mi respuesta, me gustaría volver a escribir aquí. De hecho, cada vez que leo el @Robert Israel respuesta entiendo que sé un poco acerca de los números de Fibonacci y no más!

Considere la posibilidad de $A=\pmatrix{0 & 1\cr 1 & 1\cr}$ $n$th poder de $A$, que se denota por a $A^n$, se obtiene de la siguiente manera $$ A^n = \pmatrix{F_{n-1} & F_{n}\cr F_n & F_{n+1}} . $$ donde $F_n$ $n$ésimo término de la sucesión de Fibonacci. La matriz $A$ es satisfaied en la ecuación de $x^2-x-1=0$, ya que hemos $$ \pmatrix{1 & 1\cr 1 & 2\cr}=\pmatrix{0 & 1\cr 1 & 1\cr}+\pmatrix{1 & 0\cr 0 & 1\cr} \Leftrightarrow A^2=A+I $$ Por lo tanto, obtenemos $$ A^{2n}=(A^2)^n=(A+I)^n=\sum_{j=0}^n C_j^n\,^j \etiqueta{1} $$ Ahora considere la posibilidad de la entrada de la primera fila y la segunda columna de la matriz de la ecuación de $(1)$ que impliying que $$ F_{2n}=\sum_{j=0}^n C_j^n\, F_j\, . $$

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: