¿Puede alguien ayudarme a resolver esta identidad combinatoria?

Question

Mientras intentaba deducir alguna ecuación física, me di cuenta de que era necesaria la siguiente identidad:

$\sum^{4a \leq 2k}_{a=0}{2k \choose 4a} + \sum^{4a+1 \leq 2k}_{a=0} {2k \choose 4a+1} = \left\{ \begin{array}{ll} \frac{2^k(2^k +1)}{2} & (k=4l+1, 4l+4)\\ \frac{2^k(2^k -1)}{2} & (k=4l+2, 4l+3) \end{array} \right.$

(donde $l,a$ son números enteros positivos)

Mi estrategia consistía en cambiar el $2^k$ de RHS en $\sum_{a=0}^{a=k}{k \choose a}$ y utilizar ${n \choose k}={n-1 \choose k} +{n-1 \choose k-1}$ pero sólo obtuvo relaciones incompletas y parciales. ¿Alguien puede resolver esta identidad explícitamente, o al menos sugerir otra estrategia que pueda funcionar mejor?

Answer 1

Esto es sólo una reformulación de la respuesta de André Nicolas, la pongo aquí sólo porque la estaba escribiendo cuando de repente apareció su respuesta.

La transformada discreta de Fourier da: $$1^k+i^k+(-1)^k+(-i)^k = 4\cdot\mathbb{1}_{k\equiv 0\pmod{4}} \tag{1}$$ por lo tanto: $$\mathbb{1}_{k\equiv 0,1\pmod{4}} = \frac{1}{4}\left(2+(1-i)\,i^k+(1+i)\,(-i)^k\right)\tag{2}$$ y: $$\begin{eqnarray*}\sum_{\substack{0\leq a\leq 2k\\ a\equiv{0,1}\pmod{4}}}\!\!\!\!\!\binom{2k}{a}&=&\sum_{a=0}^{2k}\binom{2k}{a}\mathbb{1}_{a\equiv 0,1\pmod{4}}\\&=&\frac{1}{2}\left(2^{2k}+(1+i)^{2k-1}+(1-i)^{2k-1}\right)\end{eqnarray*}\tag{3}$$ por lo que la afirmación se deduce considerando que $(1+i)$ es $\sqrt{2}$ veces una raíz octava de la unidad, $e^{\frac{\pi i}{4}}$ .

Answer 2

Una herramienta: Por el Teorema Binomial, tenemos $$(1+x)^n=1+\binom{n}{1}x+\binom{n}{2}x^2+\binom{n}{3}x^3+\binom{n}{4}x^4+\binom{n}{5}x^5+\cdots. \tag{1}.$$ Poner $x=1$ obtenemos una identidad familiar, y poniendo $x=-1$ obtenemos algo casi tan familiar.

Mediante suma y resta, obtenemos la suma de los coeficientes binomiales de la forma $\binom{n}{k}$ donde $k$ abarca los números pares, y también la suma donde $k$ sobre los números impar.

Ahora viene lo interesante. Pon $x=i$ . Obtenemos $$(1+i)^n=1+\binom{n}{1}i-\binom{n}{2}^2-\binom{n}{3}i+\binom{n}{4}+\binom{n}{5}i+\cdots \tag{2}.$$ Obtenemos un resultado similar utilizando $x=-i$ . También puede obtenerse a partir de (2) por conjugación.

Conectamos la ecuación (2) con potencias de $2$ . Tenga en cuenta que $1+i=\frac{1}{\sqrt{2}}\left(\cos(\pi/4)+i\sin(\pi/4)\right)$ . Tomando la $n$ -ésima potencia, obtenemos $(1+i)^n=2^{n/2}\left(\cos(n\pi/4)+i\sin(n\pi/4)\right)$ . Haga lo mismo con la sustitución $x=1-i$ . Tomando las partes real e imaginaria, obtenemos fórmulas explícitas para sumas de ciertos tipos de coeficientes binomiales.

Jugando con las ideas anteriores, podemos obtener fórmulas explícitas para $\sum \binom{n}{k}$ donde (i) $k$ oscila entre múltiplos de $4$ (ii) $k$ abarca los números que tienen resto $1$ en la división por $4$ ; $k$ abarca los números con resto $2$ en la división por $4$ (iv) $k$ abarca los números con resto $3$ .

Para el resto $0$ o $1$ (su problema) uno puede no necesitar resto $0$ y resto $1$ por separado.