Mostrar que $ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k $ es divisible por $2^n$

Question

Quiero demostrar que la $$ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k = \sum_{k=0}^{2n} \binom{2n}{k} 3^{\lceil k/2 \rceil} $$ es divisible por $2^n$.

Traté de inducción de la siguiente manera \begin{align*} \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k & = \sum_{k=0}^{n} \left( \binom{2n}{2k-1} + \binom{2n}{2k} \right) 3^k \\ & = \sum_{k=0}^{n} \left( \binom{2n-1}{2k-2} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k} \right) 3^k \\ & = 4\cdot \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k + 2\sum_{k=0}^n \binom{2n-1}{2k-1} 3^k \end{align*} ahora puedo aplicar la hipótesis de inducción a la primera parte, por lo tanto todo el primer sumando es divisible por $2^{n+1}$, si puedo demostrar que $$ \sum_{k=0}^n \binom{2n-1}{2k-1} 3^k $$ es divisble por $2^{n-1}$ me gustaría hacer. Pero aquí yo no.

Así que usted tiene sugerencias de cómo mostrar la reclamación original?

EDIT: Como se ha mencionado por la Voluntad de Orrick en los comentarios, el método inductivo funciona demasiado, acaba de demostrar la fuerte demanda que $$ \sum_{k=0}^{n}\binom{2n}{2k}3^k, \quad \sum_{k=0}^{n}\binom{2n+1}{2k}3^k, \quad \sum_{k=0}^{n}\binom{2n+1}{2k+1}3^k, \quad \sum_{k=0}^{n}\binom{2n}{2k+1}3^k \quad $$ son todos divisibles por $2^n$. Si $n = 1$ tenemos $4$, $10$, $6$ y $2$ e si $n > 1$ hemos \begin{align*} & \sum_{k=0}^{n}\binom{2n}{2k}3^k \\ & = 3 \sum_{k=0}^n \binom{2(n-1)+1}{2(k-1)+1} 3^{k-1} + \sum_{k=0}^n \binom{2(n-1)+1}{2k} 3^k \\ & = 3 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k + \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k \\ & = 3 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 3 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k+1} 3^k + \sum_{k=0}^{n-1} \binom{2(n-1)}{2k-1} 3^k + \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 3 \sum_{k=0}^{n-2} \binom{2(n-1)}{2k+1} 3^k + \sum_{k=1}^{n-1} \binom{2(n-1)}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + \sum_{k=1}^{n-1} \binom{2(n-1)}{2k-1} 3^k + \sum_{k=1}^{n-1} \binom{2(n-1)}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 6\sum_{k=0}^{n-2} \binom{2(n-1)}{2k+1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k + 6\sum_{k=0}^{n-1} \binom{2(n-1)}{2k+1} 3^k \end{align*} y ahora, por supuesto, ambas sumas son divisibles por $2^{n-1}$, y a medida que se multiplican los números que su suma es divisible por $2^n$. Similar \begin{align*} \sum_{k=0}^{n}\binom{2n+1}{2k}3^k & = \sum_{k=0}^n \left( \binom{2n-1}{2k-2} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k-1} + \binom{2n-1}{2k } \right) 3^k \\ & = \sum_{k=1}^n \binom{2n-1}{2k-2} 3^k + \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + 2\sum_{k=1}^n \binom{2n-1}{2k-1} 3^k \\ & = 3 \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + 2\sum_{k=1}^n \binom{2n-1}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2n-1}{2k} 3^k + 2\sum_{k=1}^n \binom{2n-1}{2k-1} 3^k \\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k + 6\sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k \\ \end{align*} y para las otras sumas que hemos \begin{align*} \sum_{k=0}^{n}\binom{2n+1}{2k+1}3^k & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k + 2\sum_{k=0}^n \binom{2n-1}{2k} 3^k\\ & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k+1} 3^k + 2\sum_{k=0}^{n-1} \binom{2(n-1)+1}{2k} 3^k\\ \sum_{k=0}^{n}\binom{2n}{2k+1}3^k & = 4 \sum_{k=0}^{n-1} \binom{2(n-1)}{2k+1} 3^k + 2\sum_{k=0}^{n-1} \binom{2(n-1)}{2k} 3^k \end{align*} y la hipótesis de inducción da el resultado.

Answer 1

Hágase una cadena de $2n$ luces. Suponga que cada luz puede estar apagado o puede brillar en uno de los tres colores, rojo, verde o azul, y que una cadena de luces está hecho para brillar en un color en particular por el horquillado con un par de bloques de control de ese color. Supongamos, además, que en la mayoría de un bloque de control puede ser insertado entre dos luces adyacentes (también antes de la primera luz y después de la última luz). Tenga en cuenta que los bloques de control se insertan en el mismo color los pares, sin bloques de control en el medio, y que se desprende de estas reglas que cada cadena de luces debe ser seguido por al menos uno de ellos fuera de la luz (excepto al final). Algunos ejemplos se muestran a continuación.

|GG|O|G|O|B|

OOO|RR|OO|BBBB|O

Hay $2n+1$ posiciones en las que los bloques de control puede ser colocado. Debe haber un número par, decir $2k$, de los bloques de control, y hay $\binom{2n+1}{2k}$ formas de colocación de $2k$ bloques de control. Hay $3^k$ formas de elección de los colores de la $k$ pares adyacentes de los bloques de control. Por lo tanto, el número total de configuraciones para $2n$ luces es $$ \sum_{k=0}^n\binom{2n+1}{2k}3^k. $$

Now consider adding two lights at the right end of a string. If a configuration ends with a control block, there are four ways to extend the configuration,

...*| + OO

...*| + O|R|

...*| + O|G|

...*| + O|B|

where * stands for R, G, or B. One can also move the existing control block one or two units to the right,

...* + *|O

...* + **|

(All *s take the same value, R, G, or B.) So there are six ways to extend a configuration that ended in a control block.

If the configuration did not end in a control block, there are $10$ possibilities,

...O + OO

...O + |*|O

...O + |**|

...O + O|*|

where, again, * takes one of three values, R, G, B. Since every configuration of $2n$ lights gives rise to an even number of configurations of $2n+2$ lights, the number of configurations of $2n$ lights is divisible by $2^n$.

Answer 2

$$2S(n)=(1+\sqrt3)^{2n+1}+(1-\sqrt3)^{2n+1}=(4+2\sqrt3)^n(1+\sqrt3)+(4-2\sqrt3)^n(1-\sqrt3)$$

$$\implies S(m+2)-\{(4+2\sqrt3)+(4-2\sqrt3)\}S(m+1)+(4+2\sqrt3)(4-2\sqrt3)S(m)=0$$

Answer 3

Mi enfoque fue a buscar a los valores, a ver si puedo encontrar algún patrón. Primer par de valores se $1,10,76,568,4240,\dots$. Usted puede comprobar que esto es una secuencia A107903, y se ha conocido la generación de la función $$ f(x)=\frac{1+2x}{1-8x+4x^2}. $$ Ahora, a partir de esto, usted puede fácilmente derivar de la recurrencia de la fórmula multiplicando ambos lados por $(1-8x+4x^2)$ y la comparación de los coeficientes (teniendo en $f(x)=\sum a_nx^n$). Por este método se obtiene $$a_0=1,a_1=10$$ $$a_n=8a_{n-1}-4a_{n-2}$$ A partir de esto es bastante recta hacia adelante para demostrar que el reclamo por inducción.

Única cosa que podría ser un poco claro es cómo conseguir que la generación de la función, en primer lugar, y voy a pensar acerca de eso, pero se podría llegar a la recurrencia por otros medios (tales como asumiendo que hay una recurrencia lineal y la búsqueda de sus coeficientes).

Answer 4

Creo que vale la pena señalar que la norma truco en juego aquí, lo que nos da la $$ \sum_{k=0}^{n} \binom{2n+1}{2k} 3^k = \frac{1}{2}\left((1+\sqrt3)^{2n+1}+(1-\sqrt3)^{2n+1}\right) $$ la fórmula se encuentra en otras respuestas, es aplicar el teorema del binomio para $(x+y)^n$ $(x-y)^n$ y añadir estos. Aquí, hemos \begin{align} (1 + \sqrt3)^{2n+1} &= \sum_{j=0}^{2n+1} \binom{2n+1}{j} 3^{j/2} \\ (1 - \sqrt3)^{2n+1} &= \sum_{j=0}^{2n+1} \binom{2n+1}{j} (-1)^j 3^{j/2} \\ (1 + \sqrt3)^{2n+1} + (1 - \sqrt3)^{2n+1} &= \sum_{j=0}^{2n+1} \binom{2n+1}{j} (1 + (-1)^j) 3^{j/2} \\ &= 2 \sum_{k=0}^n \binom{2n+1}{2k} 3^k \end{align} debido a $(1 + (-1)^j)$ hace $0$ por extraño $j$ $2$ incluso $j$.

---

Una vez que tenemos la fórmula con raíces cuadradas, se puede obtener una relación de recurrencia mediante la observación de que $1 \pm \sqrt3$ son las raíces de $x^2 - 2x - 2 = 0$, por lo que satisfacer $x^2 = 2x+2$$x^{n+1} = 2(x^n + x^{n-1})$.

Como resultado, si $a_n$ es cualquier combinación lineal de $(1+\sqrt3)^n$$(1-\sqrt3)^n$, sino que también satisface $a_{n+1} = 2(a_n + a_{n-1})$, y el factor de $2$ en esta recurrencia se acumula para darnos el poder de $2^n$ queremos. Hay un número de maneras de convertir esto en una prueba por inducción.