Demostrar que $2^{n-1}$ divide $\binom{n}{1} + \binom{n}{3}5 + \binom{n}{5}25 + \binom{n}{7}125 + \cdots$$n \geqslant 1$.

Question

Demostrar que $2^{n-1}$ divide $\binom{n}{1} + \binom{n}{3}5 + \binom{n}{5}25 + \binom{n}{7}125 + \cdots$$n \geqslant 1$.

Suponga $\binom{n}{k} = 0$ si $k>n$.

¿Alguien sabe de una escuela primaria de la prueba sin el uso de la fórmula de Binet?

Answer 1

Aquí está una combinatoria basada en el argumento.

Pregunta: ¿cuántas maneras hay de baldosa $1 \times (n-1)$ tablero con cuadrados en blanco y negro (que ocupan un espacio) y el rojo, el amarillo, el verde y el violeta fichas de dominó (que ocupan dos espacios)?

Respuesta 1: $2^{n-1} F_n$.

Prueba de Respuesta 1: Desde cada una de las cuatro fichas de dominó puede ser asignado a un colorante de los espacios originales como el negro o el blanco (Rojo = BB, Amarillo = WW, Verde = BW, Violeta = WB), la respuesta es la misma que el número de formas de color de cada una de las $n-1$ espacios en un $1 \times (n-1)$ directorio de blanco o de negro y, a continuación, azulejo de la junta directiva de uso de las plazas y de las fichas de dominó. Hay $2^{n-1}$ formas de color de la $n-1$ espacios, y, a continuación, $F_n$ formas mosaico de la junta con las plazas y de las fichas de dominó. Así que la respuesta es $2^{n-1} F_n$. (Aquí estamos usando el estándar de la combinatoria interpretación de los números de Fibonacci $F_n$.)

Respuesta 2: $\sum_{k \geq 0} \binom{n}{2k+1} 5^k$.

Prueba de Respuesta 2: $1 \times (n-1)$ junta ha $n$ ranuras entre los espacios (incluyendo la ranura antes de que el espacio de la primera y la ranura después de la última espacio). De los $n$ ranuras, elija un número impar $2k+1$: $a_0, a_1, a_2, \ldots, a_{2k}$. El Color negro de los espacios entre surcos $0$$a_0$, y para cada una de las $1 \leq i \leq k$, los espacios entre surcos $a_{2i-1}$$a_{2i}$. De Color blanco los espacios entre surcos $a_{2i-2}$ y $a_{2i-1}$, $1 \leq i \leq k$, así como los espacios entre surcos $a_{2k}$$n$. Por ejemplo, si $n = 11$ y elegimos surcos $1, 3, 4, 5, 9$, el colorante se verá como BWWBWBBBBW. El resultado es un colorante de la junta con el negro y el blanco de los azulejos. Por el condicionamiento en el número de transiciones desde el blanco hasta el negro, esto le da una combinatoria prueba de la conocida fórmula $\sum_{k \geq 0} \binom{n}{2k+1} = 2^{n-1}$.

Ahora, para crear un mosaico de una $1 \times (n-1)$ tablero con cuadrados en blanco y negro y nuestros cuatro colores de fichas de dominó, en primer lugar crear un mosaico de la junta con los cuadrados en blanco y negro solamente, como se describió anteriormente. A continuación, reemplazar uno o más de los WB pares que representa una transición desde los espacios en blanco a negro espacios con un color de domino. Las baldosas pueden ser fácilmente rastreadas hasta un suelo de baldosas con cuadros blancos y negros sólo mediante la sustitución de cada uno de los colores de domino con un WB par. Por ejemplo, el mosaico RRRRWWWWBW (con RR representa un rojo domino) mapas de vuelta a WBWBWWWWBW.

Si hay $k$ WB transiciones en un suelo de baldosas, entonces hay $\binom{n}{2k+1}$ maneras de seleccionar el $2k+1$ ranuras de $n$, e $5^k$ opciones para saber qué hacer con cada WB par (ya sea para mantener el BM par o reemplazarlo con uno de cuatro colores de fichas de dominó). Multiplicando juntos y sumando sobre todos los valores de $k$ da Respuesta 2.

Conclusión: Nuestros dos respuestas producir $$\sum_{k \geq 0} \binom{n}{2k+1} 5^k = 2^{n-1} F_n.$$ Puesto que los números de Fibonacci son todos los números enteros, $\sum_{k \geq 0} \binom{n}{2k+1} 5^k$ es divisible por $2^{n-1}$.

(Este argumento es una versión modificada y simplificada versión de una combinatoria prueba de una identidad similar en las Pruebas de Que Realmente Cuentan, p. 130.)

Answer 2

Esta prueba no puede calificar como de primaria, ya que utiliza parte de la teoría algebraica de números.

Deje $R=\mathbb{Z}[(1+\sqrt{5})/2]$, el anillo de enteros de $\mathbb{Q}(\sqrt{5})$, y definir $\alpha:=(1+\sqrt{5})/2$$\beta:=(1-\sqrt{5})/2\in R$.
El teorema del binomio implica $$ \begin{align*} S_n:= {n\choose 1}+5{n\choose 3}+25{n\choose 5}\ldots&=\frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2\sqrt{5}}\\ &=2^{n-1}\frac{\alpha^n-\beta^{n}}{\sqrt{5}}. \end{align*} $$ Ahora $2$ $\sqrt{5}$ son coprime, por lo $2^{n-1}$ debe dividir $S_n$$R$. Pero la única números racionales en $R$ son enteros, lo $2^{n-1}$ divide $S_n$ como enteros.

Answer 3

Tenga en cuenta que $\binom{n-2}{j-1}+2\binom{n-2}{j}+\binom{n-2}{j+1}=\binom{n}{j+1}$. Definir $$ g(n)=\sum_j \binom{n}{2j+1}\cdot5^j. $$ Entonces $$ \begin{aligned} 4g(n-2)+2g(n-1)&=4\sum_j\binom{n-2}{2j+1}\cdot5^j+2\sum_j\binom{n-1}{2j+1}\cdot5^j\\ &=(5-1)\sum_j\binom{n-2}{2j+1}\cdot5^j+2\sum_j\left[\binom{n-2}{2j}+\binom{n-2}{2j+1}\right]\cdot5^j\\ &=\sum_j\binom{n-2}{2j+1}\cdot5^{j+1}+2\sum_j\binom{n-2}{2j}\cdot5^j+\sum_j\binom{n-2}{2j+1}\cdot5^j\\ &=\sum_j\left[\binom{n-2}{2j-1}+2\binom{n-2}{2j}+\binom{n-2}{2j+1}\right]\cdot5^j\\ &=\sum_j\binom{n}{2j+1}\cdot5^j\\ &=g(n). \end{aligned} $$ Por lo $g(n)=2g(n-1)+4g(n-2)=2\left[g(n-2)+2g(n-2)\right]$ con las condiciones iniciales $g(1)=1$, $g(2)=2$. El resultado de la siguiente manera por inducción.

Sería satisfactorio para interpretar este cálculo combinatorio. Voy a pensar en esto.