Cómo entender esto combinatoriamente: $ \sum ^{2k}_{i=0} \binom {4k}{2i} (-1)^{i}=2^{2k}(-1)^{k}$

Question

Los ayudantes de mi departamento están atascados en la asistencia a un estudiante con el siguiente problema:

$$ \sum ^{2k}_{i=0} C^{4k}_{2i}(-1)^{i}=2^{2k}(-1)^{k}.$$

Intentamos resolverlo por inducción (obviamente falló), por varias identidades combinatorias, por funciones generadoras, etc. Aparte del hecho de que nada funciona, tampoco sabemos cómo resolverlo bien usando alguna interpretación combinatoria dado que esto es el HW de algún desagradecido. Me aventuro a preguntar aquí porque quiero ver cómo se puede entender correctamente.

Answer 1

Reescribiré la identidad como

$$ \sum_ {k=0}^{2n} {4n \choose 2k} (-1)^k = 2^{2n} (-1)^n$$

porque estoy a punto de usar $i$ para otra cosa. Escriba esto como

$$ \sum_ {k=0}^{4n} {4n \choose k} a_k = 4^n (-1)^n$$

donde $a_k$ es la secuencia del período $4$ que es igual a $0$ cuando $k$ es impar y que satisface $a_{2k} = (-1)^k$ .

Reclamar: $$a_k = \frac {i^k + (-i)^k}{2}.$$

Esto es esencialmente una aplicación de la la transformación discreta de Fourier . En el circuito de competición de la escuela secundaria a veces se conoce como "filtro de las raíces de la unidad".

Corolario: El LHS de la identidad evalúa a

$$ \frac {(1 + i)^{4n} + (1 - i)^{4n}}{2}.$$

Desde $(1 \pm i)^2 = \pm 2i$ tenemos $(1 \pm i)^4 = -4$ por lo tanto el LHS de la identidad evalúa a $(-4)^n$ como se desea.

Answer 2

Puede probarse mediante la inducción en $k$ :

$$ \begin {align*} \sum ^{2k}_{i=0} \binom {4k}{2i}(-1)^{i}&= \sum_ {i=0}^{2k} \left ( \sum_ {j=0}^4 \binom4j\binom {4k-4}{2i-j} \right )(-1)^i \\ &= \sum_ {j=0}^4 \binom4j\sum_ {i=0}^{2k} \binom {4k-4}{2i-j}(-1)^i \\ &= \sum_ {i=0}^{2k} \binom {4k-4}{2i}(-1)^i+4 \sum_ {i=0}^{2k} \binom {4k-4}{2i-1}(-1)^i+6 \sum_ {i=0}^{2k} \binom {4k-4}{2i-2}(-1)^i \\ & \qquad\qquad +4 \sum_ {i=0}^{2k} \binom {4k-4}{2i-3}(-1)^i+ \sum_ {i=0}^{2k} \binom {4k-4}{2i-4}(-1)^i \\ &= \sum_ {i=0}^{2k-2} \binom {4k-4}{2i}(-1)^i+6 \sum_ {i=1}^{2k-1} \binom {4k-4}{2i-2}(-1)^i+ \sum_ {i=2}^{2k} \binom {4k-4}{2i-4}(-1)^i \\ & \qquad\qquad +4 \sum_ {i=1}^{2k-2} \binom {4k-4}{2i-1}(-1)^i+4 \sum_ {i=2}^{2k-1} \binom {4k-4}{2i-3}(-1)^i \\ &= \sum_ {i=0}^{2k-2} \binom {4k-4}{2i}(-1)^i+6 \sum_ {i=0}^{2k-2} \binom {4k-4}{2i}(-1)^{i+1}+ \sum_ {i=0}^{2k-2} \binom {4k-4}{2i}(-1)^i \\ & \qquad\qquad +4 \sum_ {i=1}^{2k-2} \binom {4k-4}{2i-1}(-1)^i+4 \sum_ {i=1}^{2k-2} \binom {4k-4}{2i-1}(-1)^{i+1} \\ &=-4 \sum_ {i=0}^{2k-2} \binom {4k-4}{2i}(-1)^i \\ &=-4(-4)^{k-1} \\ &=(-4)^k\;. \end {align*}$$

Answer 3

Aquí hay una pequeña prueba.

$$ \sum_ {k=0}^{4n} \binom {4n}{k} i^k = (1+i)^{4n} = \left ( \sqrt {2} e^{i \pi /4} \right )^{4n} = 4^n e^{i n \pi } = 4^n \left ( \cos (n \pi ) + i \sin (n \pi ) \right ) = (-4)^n.$$

Al equiparar las partes reales e imaginarias se obtiene tanto la identidad de la OP

$$ \sum_ {k=0}^{2n} \binom {4n}{2k} (-1)^k = (-4)^n$$ así como la identidad del bono $$ \sum_ {k=0}^{2n-1} \binom {4n}{2k+1} (-1)^k = 0.$$

La idea aquí es, por supuesto, similar a la de la respuesta de Qiaochu Yuan.