Encontrando $\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $

Question

Ayúdame a simplificar: $$\binom{n}{0} + \binom{n}{3} + \binom{n}{6} + \ldots $$

Tengo la corazonada de que dependerá de si $n$ es un múltiplo de $6$ y es igual a $\frac{2^n+2}{3}$ cuando $n$ es un múltiplo de $6$ .

Answer 1

Esta técnica es conocida como las Raíces de la Unidad de Filtro. Ver a esta cuestión.

Tenga en cuenta que $(1+x)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}x^k$. Deje $\omega = e^{i2\pi/3}$. Entonces, tenemos:

$(1+1)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}1^k$

$(1+\omega)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^k$

$(1+\omega^2)^{n} = \displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}\omega^{2k}$

Añadir estas tres ecuaciones para obtener $\displaystyle\sum_{k = 0}^{n}\dbinom{n}{k}(1+\omega^k+\omega^{2k}) = 2^n+(1+\omega)^n+(1+\omega^2)^n$

Se puede ver que $1+\omega^k+\omega^{2k} = 3$ si $k$ es un múltiplo de a $3$ $0$ lo contrario.

Por lo tanto, $\displaystyle\sum_{m = 0}^{\lfloor n/3 \rfloor}\dbinom{n}{3m} = \dfrac{1}{3}\left[2^n+(1+\omega)^n+(1+\omega^2)^n\right]$

Ahora, simplificar esto.

Answer 2

He aquí un método que no implica (explícitamente) números complejos.

Dejemos que $A_n=\sum_k \binom{n}{3k}$ , $B_n=\sum_k \binom{n}{3k+1}$ , $C_n=\sum_k \binom{n}{3k+2}$ .

Entonces $A_n+B_n+C_n=2^n$ por el teorema del binomio. Además, la identidad de Pascal implica lo siguiente: $$ \begin{eqnarray} A_n&=&A_{n-1} + C_{n-1} =2^{n-1}-B_{n-1} \\ B_n&=&B_{n-1} + A_{n-1} = 2^{n-1}-C_{n-1} \\ C_n&=&C_{n-1} + B_{n-1} = 2^{n-1}-A_{n-1} \end{eqnarray} $$ Poniendo todo esto junto, $$A_n = 2^{n-1}-(2^{n-2} - C_{n-2})=2^{n-2} + C_{n-2} = 2^{n-2} + 2^{n-3} - A_{n-3} = 3(2^{n-3}) - A_{n-3} \, .$$ También, $A_0=A_1=A_2=1$ .

De ello se desprende que $A_{3n}=3(2^{n-3}-2^{n-6}+\dots \pm 2^0) \mp 1$ con expresiones similares para $A_{3n+1}$ y $A_{3n+2}$ . Obviamente, se podría utilizar una fórmula de serie geométrica para simplificar aún más esto.

Answer 3

El $n$ la suma es $\dfrac{2^n+2\cos(n\pi/3)}3$ . Tenga en cuenta que $2\cos(n\pi/3)$ siempre está en $\{-2,-1,1,2\}$ y, que, a partir de $n=0$ Es decir, es $2$ , $1$ , $-1$ , $-2$ , $-1$ , $1$ , $2$ , $1$ , $-1$ , $-2$ , $-1$ , $1$ , $2$ , $1$ etc.

Para ver por qué, utilice la tercera raíz unitaria $$1,\qquad \mathrm j=\mathrm e^{2\mathrm i\pi/3},\qquad\mathrm j^2=\mathrm e^{-2\mathrm i\pi/3},$$ y que $1+\mathrm j^k+\mathrm j^{2k}=0$ por cada $k$ excepto cuando $k$ es un múltiplo de $3$ y luego $1+\mathrm j^k+\mathrm j^{2k}=3$ .

Así, la suma $S_n$ para calcular las soluciones $$3S_n=\sum_k{n\choose k}(1+\mathrm j^k+\mathrm j^{2k})=\sum_k{n\choose k}+\sum_k{n\choose k}\mathrm j^k+\sum_k{n\choose k}\mathrm j^{2k},$$ es decir, $$3S_n=(1+1)^n+(1+\mathrm j)^n+(1+\mathrm j^2)^n. $$ Identificación de $1+\mathrm j=\mathrm e^{\mathrm i\pi/3}$ y $1+\mathrm j^2=\mathrm e^{-\mathrm i\pi/3}$ permite deducir que $$(1+\mathrm j)^n+(1+\mathrm j^2)^n=\mathrm e^{n\mathrm i\pi/3}+\mathrm e^{-n\mathrm i\pi/3}=2\cos(n\pi/3), $$ lo que concluye la prueba.

Answer 4

Si $1+\zeta+\zeta^2=0$ , intente calcular $(1+\zeta^0)^n + (1+\zeta)^n + (1+\zeta^2)^n$ . Pista: $\zeta^3=1$ y, si $k$ no es divisible por $3$ , $1+\zeta^k+\zeta^{2k}=0$ .

Answer 5

Quería publicar esto como un comentario pero no me deja, así que por favor, no te preocupes por mí.

Los coeficientes binomiales aparecen en el triángulo de Pascal, lo que sugiere que existe una relación de recurrencia para $\sum_{i = 0}^{\lceil \frac{n}{3} \rceil} \binom{n}{3i}$ y de hecho lo hay. He mirado en http://oeis.org/A024493 y lo encontré: $a(0) = 1$ , $a(1) = 1$ , $a(2) = 1$ , $a(n) = 3a(n - 1) - 3a(n - 2) + 2a(n - 3)$ .