Las filas pares e impares (casi) en el Pascal ' triángulo s

Question

Me encontré con la siguiente proposición:

$\binom{n}{k}$ es incluso para todos los $1 ≤ k ≤ n-1$ fib $n=2^m$ algunos $m \in \mathbb N$

$\binom{n}{k}$ es extraño que todos los $0 ≤ k ≤ n$ fib $n=2^m-1$ algunos $m \in \mathbb N_0$

Supongo que uno podría demostrar que el uso de la de Lucas teorema o la ordenada hecho de que

$$ \mbox{(#Impar de entradas en } n^{th} \mbox{ fila del triángulo de Pascal)} = 2^{\mbox{(#1 en la representación binaria de $n$)}} $$

Sin embargo, parece ser una exageración, en este caso (y en el libro que yo uso no introducir el teorema). Me pregunto si hay una forma de demostrar la proposición en la mano directamente.

Cualquier ayuda es muy apreciada.

Answer 1

Sugerencia: Tenga en cuenta primero que si es impar para $\binom{2^m-1}k$ $0\le k\le 2^m-1$, entonces automáticamente $\binom{2^m}k$ es incluso para $1\le k\le 2^m-1$, desde $\binom{2^m}k=\binom{2^m-1}{k-1}+\binom{2^m-1}k$.

Ahora usar identidad de Pascal generalizado,

$$\binom{n}k=\sum_{i=0}^r\binom{r}i\binom{n-r}{k-i}$$

$n=2^{m+1}-1$ y $r=2^m$:

$$\binom{2^{m+1}-1}k=\sum_{i=0}^{2^m}\binom{2^m}i\binom{2^m-1}{k-i}\;.$$

De la hipótesis de inducción sabes la paridad de cada coeficiente binomial en suma en el lado derecho.

(Si no has visto la identidad de Pascal generalizado antes, se puede fácilmente comprobar por inducción en $r$.)

Answer 2

En realidad, se puede ver en el triángulo en sí mismo que no es una diagonal de los números impares, empezando con el 1 en la fila $2^k$ y llegando a la fila $2^{k+1} -1.$, de Modo que cada fila entre tiene una extraña entrada, este ser por el simple propagación. Empezando por la fila 4, diagonal impar de entradas: 1,5,15,35. O, empezando por la fila 8: 1,9,45, 165,495,1287,3003,6435.

En la misma nota, no es una diagonal de números de fila $2^k$ $2^{k+1}-2.$De la fila 4: 4,10,20. Desde la fila 8: 8,36,120,3309,792,1716,3432.

Supongo que usted necesita para trabajar de lo que sucede en la fila $2^k$ y la de la fila $2^k - 1$ por su propia cuenta. La vida es una interminable búsqueda de la renovación. Sin embargo, sí puede hacerlo por Legendre del teorema de $\mbox{ord}_2 (n!)$ usando una suma de piso funciones, en el caso de que $n = 2^k.$, Entonces el hecho de que la fila $2^k -1$ son de todos los impares es sólo la inducción.

EDIT: veo, @Tomás da una respuesta muy sencilla para la fila $2^m,$, por lo que hay que ir.

=-=-=-=-=-=-=-=-=-=-=

=-=-=-=-=-=-=-=-=-=-=

Answer 3

Es fácil demostrar que $(1+x)^{2^m} = 1+x^{2^m}$ $\mathbb Z_2[x]$ % todo $m$por inducción.

Ahora necesita demostrar que no es verdad $n$ no una potencia de $2$.

Si $n=2^m q$ $q>1$ Dónde está extraño y $m\geq 0$ y $(1+x)^{2^mq}= (1+x^{2^m})^q = 1+qx^{2^m} +\dots$. $q$ Es extraño, eso significa que $\binom{n}{2^m}$ es impar.

Este resultado se generaliza a todos los primos $p$. Si es divisible por $\binom n k$ $p$ $1\leq k\leq n-1$ $n=p^m$ $m$. Otra vez usted puede probar por inducción que $(1+x)^{p^m}=1+x^{p^m}$ $\mathbb Z_p[x]$, otra vez usted demostrar que $\binom{p^mq}{p^m}\equiv q\pmod p$.