Triángulo de Pascal y Representaciones Binarias

Question

En el artículo que estoy leyendo actualmente, se afirma como un hecho bien conocido que las posiciones de los $2^i$ o, equivalentemente, $(n-2^i)$ $n^{th}$ fila en el Triángulo de Pascal modulo $2$ deletrear la representación binaria de $n$: $$ \newcommand{\rojo}{\color{rojo}} \newcommand{\blue}{\color{blue}} \begin{array}{rrc} 0:&0&1\\ 1:&1&\red1\ 1\\ 2:&10&\blue1\ \red0\ 1\\ 3:&11&1\ \blue1\ \red1\ 1\\ 4:&100&\red1\ 0\ \blue0\ \red0\ 1\\ 5:&101&1\ \red1\ 0\ \blue0\ \red1\ 1\\ 6:&110&1\ 0\ \red1\ 0\ \blue1\ \red0\ 1\\ 7:&111&1\ 1\ 1\ \red1\ 1\ \blue1\ \red1\ 1\\ 8:&1000&\blue1\ 0\ 0\ 0\ \red0\ 0\ \blue0\ \red0\ 1\\ 9:&1001&1\ \blue1\ 0\ 0\ 0\ \red0\ 0\ \blue0\ \red1\ 1\\ 10:&1010&1\ 0\ \blue1\ 0\ 0\ 0\ \red0\ 0\ \blue1\ \red0\ 1 \end{array} $$ Para ser más precisos y/o técnico, si $n$'s binarias de expansión de la es $b_t b_{t-1}\cdots b_1 b_0$ o, equivalentemente, $ n=\sum_{i=0}^t b_i\cdot 2^i $ entonces tenemos $$ b_i=\binom n{2^i}\pmod 2 $$

---

Ahora estaba pensando en el más limpio y más sencilla manera de demostrar este resultado. Me parece la auto-similitud de Sierpinski del Triángulo para proporcionar una visual agradable argumento, sin embargo, no será sencillo para comunicarse succintly en un papel, creo.

Mi sugerencia de prueba

Por lo tanto pensé que sería más sencillo considerar la posibilidad de que los poderes de $2$ brecha, respectivamente, el numerador y el denominador de $$ \binom n{2^i}=\frac{\prod_{s=1}^{2^i}(n-2^i+s)}{\prod_{t=1}^{2^i} t} $$

Ahora tenga en cuenta que los factores del numerador $n-2^i+s$ cubierta de un conjunto completo de residuos módulo $2^i$. Los no-cero resto $n-2^i+s\equiv t$ modulo $2^i$ tendrá el mismo divisibilidad por $2$$t$, es decir, algunos de potencia $2^j<2^i$ será la máxima potencia de $2$ dividir ambos $t$ y ese factor.

Exactamente uno de los factores será divisible por $2^i$, es decir, el único factor de $n-2^i+s$ cuya representación binaria termina en $i$ ceros. Ahora bien, si el $i^{th}$ bit es cero, entonces este factor, al menos, ser divisible por $2^{i+1}$ porque entonces termina en, al menos, $i+1$ ceros. Por otro lado, si el $i^{th}$ bit es $1$, este factor es divisible por ningún poder superior de $2$$2^i$.

Así vemos que si el $i^{th}$ bit es $1$ no es un 1:1 correspondencia entre los factores del numerador y el denominador con respecto a su divisibilidad por $2$, lo que resulta en un número impar. Pero si el $i^{th}$ bit es cero, entonces el numerador tiene al menos un factor más de $2$ que el numerador - contadas por la multiplicidad.

---

Pregunta: ¿tiene usted sugerencias para simplificar este argumento o puede que me apunte a un enfoque completamente diferente de lo que hace todo más sencillo? Tal vez hay incluso un lugar limpio y simple combinatoria de la prueba?

Answer 1

No estoy seguro de que podría ser un enfoque más sencillo, pero de una forma alternativa de mostrar esto podría ser buscar en los patrones de las diagonales que expresan la $\binom {n}{2^i} $ coefficiens para un determinado $i $ (correctamente destaca por los colores en el triángulo), y para mostrar que ellos son idénticos a los patrones seguidos por la $i^{th}$ dígitos (desde la derecha) de la secuencia de números binarios.

Por ejemplo, es sencillo observar que el $1^{st} $ dígito de la derecha (es decir, la última) en la secuencia de los números binarios, sigue un modelo de alternancia $10101010...$ periodo $2$, lo cual refleja el comportamiento del progresivo aumento de los números de $\mod 2$. Un patrón idéntico es seguido por la diagonal que expresan la $\binom {n}{1} \mod 2 $ coeficientes (o, equivalentemente, el $\binom {n}{n-1} \mod 2$ coeficientes), ya que corresponde a la secuencia de $n \mod 2$.

Generalizando, el $i^{th} $ dígito de la derecha en la secuencia de los números binarios, sigue un modelo de alternancia con el período de $2^i$ en el que el primer $2^{i-1}$ elementos se $1$ y el segundo $2^{i-1}$ elementos se $0$. Esto puede ser demostrado por la observación de que, para cualquier número binario $K $, si la cantidad de $K \mod 2^i $ $<2^{i-1} $ $i^{th} $ dígito de la derecha debe ser necesario $0$, mientras que si $K \mod 2^i $ $\geq 2^{i-1} $ $i^{th} $ dígito de la derecha debe ser necesario $1$. También, ya que en la secuencia de números binarios la $i^{th} $ dígito de la derecha compara por primera vez en $2^{i-1}$, la secuencia empieza con $1$.

Un patrón similar existe para la diagonal de expresar el $\displaystyle \binom {n}{2^{i-1}} \mod 2 $ coeficientes, o, equivalentemente, el $\displaystyle \binom {n}{n-2^{i-1}} \mod 2$ de los coeficientes. Estas diagonales empezar a $n= 2^{i-1}$ y, en el original triángulo de Pascal (no $\mod 2$) tienen coeficientes correspondientes a la secuencia $\binom {n}{2^{i-1}}$ por $i$ y el aumento de la $n$. Esta secuencia puede ser escrito como

$$1$$ $$n+1$$ $$\frac { (n+1)(n+2)}{2}$$ $$\frac {(n+1)(n+2)(n+3)}{2 \cdot 3} $$ $$\frac {(n+1)(n+2)(n+3).....(n+j)}{2 \cdot 3 \, ...... \cdot j}$$

y así sucesivamente. No es difícil mostrar que el numerador y el denominador en esta secuencia tiene el mismo divisibilidad por $2$ (es decir, su proporción es $\mod 2 = 1$) hasta que en el numerador llegar a la $n + 2^{i-1}= 2^i$ plazo y en el denominador el $2^{i-1}$ plazo. A partir de este punto, el numerador contiene el factor de $2$ una vez más que el denominador, y tenemos que la proporción es $\mod 2 = 0$. Esto continúa hasta que en el numerador llegar a la $n + 2^{i}=2^{i-1}+2^{i}$ plazo y en el denominador el $2^{i}$ plazo, donde el denominador se obtiene un factor de $2$ más que en el numerador y encontramos de nuevo que la proporción es $\mod 2=1$, y así sucesivamente. Tal regularidad conduce a que el patrón descrito anteriormente, idéntica a la de la $i^{th}$ dígito de la derecha en los números binarios.