¿Cómo demuestro que hay infinitas filas del triángulo de Pascal con sólo números Impares?

Question

Este es el ejercicio número $59$ del capítulo $2$ de Hugh Gordon Probabilidad discreta .

Demuestre que hay infinitas filas del Triángulo de Pascal que consisten enteramente en números Impares.

Intuitivamente, si se dibujan recuadros alrededor de los números del triángulo de Pascal y se colorean los recuadros en negro si el número es impar y en blanco si el número es par, entonces el triángulo tendrá el aspecto siguiente Triángulo de Sierpinsky a medida que se aleja.

En particular, si numeramos las filas empezando por la parte superior como $1$ las filas serán todos los números Impares exactamente las filas con número $2^n$ para algunos $n \in \mathbb{N}$ (o $n=0$ para la primera). Puedes ver esto si piensas en la coloración del triángulo de Sierpinsky.

De todos modos, ¿hay alguna forma directa de mostrar lo siguiente para todos $k$ con $0 \leq k \leq 2^n-1$ ?

$$\binom{2^n-1}{k} \equiv 1 \pmod{2}$$

Probablemente se pueda hacer por inducción, pero sería preferible una prueba directa.

Answer 1

Módulo $2$ ,

$$(1+x)^{2^n-1} = \frac{(1+x)^{2^n}}{1+x} = \frac{1+x^{2^n}}{1+x}=1+x+x^2+ \dots + x^{2^n-1}. \qquad\blacksquare$$

---

También, modulo un primo impar $p$ ,

$$(1+x)^{p^n-1} = \frac{(1+x)^{p^n}}{1+x} = \frac{1+x^{p^n}}{1+x}= \frac{1-(-x)^{p^n}}{1-(-x)} = 1 - x+x^2- \dots + x^{p^n-1},$$

que muestra que $${p^n-1 \choose k} \equiv (-1)^k \pmod p.$$

Answer 2

Con fines ilustrativos; ciertamente parece que las filas $2^k - 1$ son una buena apuesta. Yo revisaría el problema y señalaría que todos los pares, excepto el inicial y el final $1,$ parece ser filas $2^k$ sólo.

Lo dibujé inicialmente para encontrar el número total de regalos en la canción "Los doce días de Navidad". Recuerdo que se lo conté a mi padre hace veinte o treinta años, y que se quejó: "¿Por qué es el binomio (14,3)? Son 12 días, ¿cómo tiene sentido 14?". Mucho más tarde, conseguí papel cuadriculado (cuadrille) e hice la versión más legible que pude e hice un jpeg. Me gusta, especialmente, cómo la fila 14 tiene coeficientes consecutivos 1001,2002,3003. Una buena razón para esto, basándose en $7 \cdot 11 \cdot 13 = 1001.$

Answer 3

Pista

esta propiedad se deduce del hecho de que si $m+n=2^k-1$ no hay "cargas" en la adición.

el poder de $2$ que divide $a!$ es simplemente $a-\sigma_2(a)$ donde $\sigma_2(a)$ devuelve la suma de los dígitos binarios de $a$

Answer 4

$\binom{2^n-1}{k}=\frac{(2^n-k)\cdot\dots (2^n-2)\cdot(2^n-1)}{1\cdot 2 \cdot 3 \dots k}$ nota que $\bmod 2^n$ el último número de arriba es congruente con el primero multiplicado por menos $1\bmod 2^n$ el penúltimo de arriba es congruente con el segundo de abajo multiplicado por menos uno $\bmod 2^n$ . Como no hay ningún factor divisible por $2^n$ en la división la congruencia $\bmod 2^n$ nos da toda la divisibilidad que necesitamos $\bmod 2^n$ . Desde $m$ y $-m$ son igualmente divisibles por $2^n$ se anulan como he dicho.

Answer 5

Will Jagy me inspiró esta solución. Fíjate en los términos de $\binom{2^n}{k}$ son siempre iguales a menos que $k=0$ o $2^n$ .

Utilizando la recurrencia pascal (y el triángulo) , el hecho $\binom{2^n-1}{1}$ es impar y todos los términos bajo esa fila son pares concluimos que el número a la derecha de ese es impar, y repitiendo el término a la derecha de ese es impar....