Secuencia recursiva módulo 4

Question

Para todos los enteros positivos Impares $k$ defino una secuencia recursiva mediante $$ d_k=2+ {k\choose 1}d_{k-2} + {k\choose 2}d_{k-4} + \dots +{k\choose \frac{k-1}{2}}d_1\\ d_1=2 $$

Quiero estudiar esta secuencia modulo $4$ . Por inducción, es fácil ver que $d_k$ es $0$ o $2$ . Calculando esta secuencia obtengo $$ 2,0,2,2,0,2,2,0,2,2,0,2,2,0,2\dots (\mod 4) $$ lo que me hizo pensar que $$ d_k\equiv 0 (\mod 4)\text{ if and only if } k\equiv 0 (\mod 3) $$

¿Tienes una idea de cómo demostrarlo? He intentado demostrarlo pero no encuentro ningún comportamiento agradable en los coeficientes del binomio que me ayude.

Answer 1

Descargo de responsabilidad: Lo siguiente es más un comentario largo que una respuesta. Lo actualizaré si averiguo algo más.

Desde que dijo eso $d_k$ es $0$ o $2$ modulo $4$ es lo mismo que decir que $d_k$ es uniforme, permítame replantear su problema. Defina $$ \begin{align} c_n &= 1 + \binom{2n+1}{1} c_{n-1} + \dotsc + \binom{2n+1}{n}c_0\\ c_0 &= 1 \end{align} $$ para que $d_{2n+1} = 2c_n$ por cada $n \geq 0$ . Entonces su pregunta equivale a preguntar si $$ c_n \text{ is even } \quad \text{iff} \quad n \equiv 1 \pmod 3. $$ Esto podría ser útil porque, como consecuencia de Teorema de Lucas , $\binom{k}{i}$ es par si y sólo si al menos uno de los dígitos binarios de $i$ es mayor que el dígito correspondiente de $k$ . En otras palabras, $\binom{k}{i}$ es par si y sólo si las expansiones binarias de $k-i$ y $i$ tener un $1$ en el mismo lugar (véase también esta respuesta en MSE). Utilicé esto para escribir un código para calcular $c_n$ razonablemente rápido y comprobado que su conjetura se mantiene al menos para la primera $10000$ términos de la secuencia, pero no tengo una prueba, todavía.

También puede ser útil observar que los coeficientes binomiales de impar, cuando se disponen en el triángulo de Pascal, forman una aproximación al triángulo de Sierpinski (puede encontrar una prueba aquí ).

Answer 2

Como en la respuesta de @A.P., definir $$ \begin{eqnarray} c_0 & = & 1 \\ c_n & = & 1 + \sum_{k = 1}^n {2n + 1 \choose k}c_{n - k} \end{eqnarray} $$ para que $ d_{2n + 1} = 2c_n $ . Demostremos por inducción que $ c_n $ es par si $ n \equiv 1 \mod 3 $ .

$ \bullet $ Inicialización: $ c_0 = 1 $ es impar.

$ \bullet $ Inducción: Tenemos $$ \begin{eqnarray} c_n & = & 1 + \sum_{k = 1}^n {2n + 1 \choose k}c_{n - k} \\ & \equiv & 1 + \sum_{k \in [\![1, n]\!], k \not\equiv n - 1\mod 3} {2n + 1 \choose k} \\ & = & 1 + \frac{\sum_{k = 1}^{2n} {2n + 1 \choose k}}2 - \sum_{k \in [\![1, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \\ & = & 2^{2n} - \sum_{k \in [\![1, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \\ & \equiv & \sum_{k \in [\![1, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \mod 2 \\ & \equiv & \sum_{k \in [\![0, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} + \begin{cases}1 \text{ if $ 3 \mid n - 1 $} \\0 \text{ otherwise}\end{cases} \mod 2 \end{eqnarray} $$ Observe además que $ k \equiv n - 1 \mod 3 \implies 2n + 1 - k \equiv n - 1 \mod 3 $ . Por lo tanto, $$ \begin{eqnarray} c_n \equiv \begin{cases}0 \text{ if $ 3 \mid n - 1 $} \\1 \text{ otherwise}\end{cases} \mod 2 & \iff & \sum_{k \in [\![0, n]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \equiv 1 \mod 2 \\ & \iff & \sum_{k \in [\![0, 2n + 1]\!], k \equiv n - 1\mod 3} {2n + 1 \choose k} \equiv 2 \mod 4 \end{eqnarray} $$ Ahora denota $$ r_{a, m} = \sum_{k \in [\![0, m]\!], k \equiv a\mod 3} {m \choose k} $$ $ r $ se comporta como un triángulo de Pascal enrollado. Es decir, $ r_{a + 1, m + 1} = r_{a, m} + r_{a + 1, m} $ y $ r_{a + 3, m} = r_{a, m} $ . Así, podemos calcular fácilmente $ r_{0, m}, r_{1, m}, r_{2, m} $ modulo $ 4 $ $$ \begin{eqnarray} m\quad & r_0 & r_1 & r_2 \\ 0\quad & 1 & 0 & 0 \\ 1\quad & 1 & 1 & 0 \\ 2\quad & 1 & 2 & 1 \\ 3\quad & 2 & 3 & 3 \\ 4\quad & 1 & 1 & 2 \end{eqnarray} $$ Vemos que entra en un ciclo de periodo $ 6 $ a partir de $ m = 2 $ y que $ r_{n - 1, 2n + 1} $ es siempre $ 2 $ como se quiera.

Nota: El patrón sugiere altamente que probar $ c_n \equiv c_{n - 1} + c_{n - 2} \mod 2 $ es una opción, pero no pude encontrar la manera de hacerlo funcionar.