Demostrar la identidad combinatoria $\sum_{k=0}^{n}(-1)^k \binom{2n-k}k 2^{2n-2k} = 2n+1$ "directamente"

Question

Es un problema de deberes. En la primera parte del problema, he conseguido utilizar un problema combinatorio para demostrar la siguiente identidad:

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

Pero en realidad tengo problemas con la segunda parte del problema que me pedía demostrar esta identidad "directamente", probablemente utilizando alguna forma de funciones generadoras/método de álgebra.

Me dieron una pista, pero me quedé atascado: La pista dice que calcule

$\Sigma_{n=0}^\infty\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} x^{2n}$

y que sería útil considerar el hecho de que $ \Sigma(2n+1)x^{2n}= \frac{d}{dx}\frac{x}{1-x^2} $ y $(1-x)^{-a-1}=\Sigma_{j=0}^\infty {a+j \choose j}x^j$ .

Soy capaz de demostrar estos dos "hechos posiblemente útiles" en la pista, pero no veo cómo calcular la suma doble sugerida o demostrar la identidad. [¡Habría pensado que la prueba combinatoria es más difícil de encontrar!] [Puedes suponer que estoy familiarizado con el tratamiento formal de las series de potencias].

Cualquier ayuda será muy apreciada.

Answer 1

Queremos demostrar que $$\sum_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$$

Trabajemos hacia atrás. La aproximación mediante funciones generadoras consiste en demostrarlo de una vez para todos $n$ en lugar de un $n$ hemos terminado si podemos demostrar que $$\sum_{n=0}^{\infty} \sum_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} x^{2n} = \sum_{n=0}^{\infty} (2n+1) x^{2n} = \frac{d}{dx} \frac{x}{1-x^2}$$

Ahora bien, obviamente para sumar lo anterior tal y como está escrito, necesitamos resolver el problema original, así que eso no sirve de nada. En su lugar, vamos a intercambiar las sumas, para sumar sobre $k$ en su lugar (y también escribir $\binom{2n-k}{k}$ como $\binom{2n-k}{2n-2k}$ para obtener una expresión más bonita): queremos demostrar que $$\sum_{k=0}^\infty (-1)^k \sum_{n=k}^{\infty} \binom{2n-k}{2n-2k} 2^{2n-2k} x^{2n} = \frac{d}{dx} \frac{x}{1-x^2}$$

Ahora dejemos que $j = n - k$ de modo que $n = k + j$ entonces nuestra suma interna anterior es $$\sum_{j=0}^{\infty} \binom{k+2j}{2j}2^{2j}x^{2k+2j} = x^{2k}\sum_{j=0}^{\infty} \binom{k+2j}{2j}(2x)^{2j}$$

Esta suma tiene sólo los términos pares de una suma de la forma de la segunda pista, y escogiendo sólo los términos pares de una serie de potencias $f(x)$ da $\frac{f(x)+f(-x)}{2}$ . Por lo tanto, la suma anterior es

$$x^{2k}\left(\frac{(1-2x)^{-k-1} + (1+2x)^{-k-1}}{2} \right)$$

Y la suma total se convierte en

$$\sum_{k=0}^{\infty} (-1)^k x^{2k} \left(\frac{(1-2x)^{-k-1} + (1+2x)^{-k-1}}{2} \right)$$ $$= \frac12\left(\frac{1}{1-2x}\sum_{k=0}^\infty\left(\frac{-x^2}{1-2x}\right)^k + \frac{1}{1+2x}\sum_{k=0}^\infty \left(\frac{-x^2}{1+2x}\right)^k\right)$$ $$ = \frac12\left(\frac{1}{1-2x}\frac{1}{1-\frac{-x^2}{1-2x}} + \frac{1}{1+2x}\frac{1}{1-\frac{-x^2}{1+2x}}\right)$$ $$ = \frac12\left( \frac{1}{1-2x+x^2} + \frac{1}{1+2x+x^2}\right)$$ $$ = \frac12\left( \frac{1}{(1-x)^2} + \frac{1}{(1+x)^2}\right) \tag 1$$

Sólo queda demostrar que esto es lo mismo que $\dfrac{d}{dx} \dfrac{x}{1-x^2}$ que es un simple ejercicio de cálculo.

Answer 2

Supongamos que intentamos evaluar $$\sum_{k=0}^n {2n-k\choose k} (-1)^k 4^{n-k}.$$

Introducir la representación integral $${2n-k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^{2n-k} \; dz.$$

Esto da para la suma la integral $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \sum_{k=0}^n \frac{(-1)^k 4^{n-k}}{z^k (1+z)^k} \; dz \\ = \frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{1-(-1)^{n+1}/4^{n+1}/z^{n+1}/(1+z)^{n+1}} {1+1/4/z/(1+z)} \; dz \\ = \frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{4z+4z^2-(-1)^{n+1}/4^n/z^n/(1+z)^n} {1+4z+4z^2} \; dz.$$

Esto tiene dos componentes. El primer componente es $$\frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{4z+4z^2}{(1+2z)^2} \; dz = \frac{4^{n+1}}{2\pi i} \int_{|z|=\epsilon} (1+z)^{2n+1} \frac{1}{(1+2z)^2} \; dz,$$ que se ve fácilmente que es cero.

El segundo componente es $$\frac{4^n}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{(-1)^n/4^n/z^n/(1+z)^n} {(1+2z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n}}{z} \frac{(-1)^n/z^n/(1+z)^n} {(1+2z)^2} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \frac{(-1)^n} {(1+2z)^2} \; dz.$$

Extrayendo los coeficientes obtenemos $$(-1)^n \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} (n-q+1).$$ Esto se convierte en $$(-1)^n (n+1) \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} - (-1)^n \sum_{q=0}^n {n\choose q} (-1)^{n-q} 2^{n-q} q.$$ o $$(n+1)- (-1)^n \sum_{q=1}^n {n\choose q} (-1)^{n-q} 2^{n-q} q \\ = (n+1)- (-1)^n \times n\times \sum_{q=1}^n {n-1\choose q-1} (-1)^{n-q} 2^{n-q} \\ = (n+1)- (-1)^n \times n\times \sum_{q=1}^n {n-1\choose q-1} (-1)^{(n-1)-(q-1)} 2^{(n-1)-(q-1)} \\ = (n+1)- (-1)^n \times n\times (-1)^{n-1} = 2n+1.$$

La elección de $\epsilon$ aquí es tal que $\epsilon \lt 1/2.$