Demuestra la siguiente relación:

Question

Debo demostrar la relación $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$

Llegué hasta aquí antes de quedarme atascado:

$\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & \sum_{k=0}^{n+1}\left\{\binom{n+k}{k}+\binom{n+k}{k-1}\right\}\frac1{2^k}\\ & = & \sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k}{k-1}\frac1{2^k}+\binom{2n+1}{n}\frac1{2^k}. \end{eqnarray*}$

Si puedo combinar el segundo y el tercer término y obtener algo igual que el primer término, he terminado, pero no he podido hacerlo.

Answer 1

Dejemos que $s_n=\displaystyle\sum_{k=0}^n\binom{n+k}k\frac1{2^k}$ . Entonces

$$\begin{align*} s_{n+1}&=\sum_{k=0}^{n+1}\binom{n+k+1}k\frac1{2^k}\\ &=\sum_{k=0}^{n+1}\left(\binom{n+k}k+\binom{n+k}{k-1}\right)\frac1{2^k}\\ &=\binom{2n+1}{n+1}\frac1{2^{n+1}}+\sum_{k=0}^n\binom{n+k}k\frac1{2^k}+\sum_{k=0}^n\binom{n+1+k}k\frac1{2^{k+1}}\\ &=\binom{2n+1}{n+1}\frac1{2^{n+1}}+s_n+\frac12\sum_{k=0}^n\binom{n+1+k}k\frac1{2^k}\\ &=s_n+\frac12\left(s_{n+1}-\binom{2n+2}{n+1}\frac1{2^{n+1}}\right)+\binom{2n+1}{n+1}\frac1{2^{n+1}}\\ &=s_n+\frac12s_{n+1}+\binom{2n+1}{n+1}\frac1{2^{n+1}}-\binom{2n+2}{n+1}\frac1{2^{n+2}}\;, \end{align*}$$

y por lo tanto

$$\begin{align*} s_{n+1}&=2s_n+\binom{2n+1}{n+1}\frac1{2^n}-\binom{2n+2}{n+1}\frac1{2^{n+1}}\\ &=2s_n+\frac1{2^{n+1}}\left(2\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\right)\\ &=2s_n+\frac1{2^{n+1}}\left(2\binom{2n+1}{n+1}-\binom{2n+1}{n+1}-\binom{2n+1}n\right)\\ &=2s_n+\frac1{2^{n+1}}\left(\binom{2n+1}{n+1}-\binom{2n+1}n\right)\\ &=2s_n\;. \end{align*}$$

Answer 2

Has utilizado correctamente la identidad de Pascal, pero luego te has equivocado al pasar a la siguiente línea. (Debería tener un $n$ en ese último exponente de $2$ no un $k$ .) Sin embargo, recomiendo ir por otro camino.

$\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & \sum_{k=0}^{n+1}\left\{\binom{n+k}{k}+\binom{n+k}{k-1}\right\}\frac1{2^k}\\ & = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^{n+1}\binom{n+k}{k-1}\frac1{2^k}\\ & = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=1}^{n+1}\binom{n+k}{k-1}\frac1{2^k}\\ & = & \sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^n\binom{n+k+1}{k}\frac1{2^{k+1}}\\ & = & -\binom{2n+2}{n+1}\frac1{2^{n+2}}+\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^{k+1}}\\ & = & -\binom{2n+2}{n+1}\frac1{2^{n+2}}+\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}+\frac12\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}. \end{eqnarray*}$

¿Ves cómo ahora tenemos la mitad de la suma original en el lado derecho? Si restamos eso y luego multiplicamos por $2$ tenemos

$\begin{eqnarray*} \sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k} & = & -\binom{2n+2}{n+1}\frac1{2^{n+1}}+2\sum_{k=0}^{n+1}\binom{n+k}{k}\frac1{2^k}\\ & = & -\binom{2n+2}{n+1}\frac1{2^{n+1}}+2\binom{2n+1}{n+1}\frac1{2^{n+1}}+2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}. \end{eqnarray*}$

Finalmente, aplicando la identidad de Pascal a $\binom{2n+2}{n+1}$ y utilizando el hecho de que $\binom{2n+1}{n}=\binom{2n+1}{n+1},$ los coeficientes binomiales extraños se cancelan, y nos quedamos con $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k},$$ como se desee.

Answer 3

A modo de enriquecimiento, aquí hay otra prueba algebraica utilizando variables variables complejas.

Supongamos que intentamos demostrar que $$\sum_{k=0}^{n+1} {n+1+k\choose k} \frac{1}{2^k} = 2 \sum_{k=0}^n {n+k\choose k} \frac{1}{2^k}.$$

Introducir las representaciones integrales $${n+1+k\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1+k}}{z^{k+1}} \; dz.$$

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

Ahora el primer término del numerador da claramente una contribución nula por lo que obtenemos $$2\times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{n+1}}{1-z} \frac{(1+z)^{n+2}}{z^{n+2} 2^{n+2}} \; dz \\ \frac{1}{2^{n+1}} \times \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2n+3}}{1-z} \frac{1}{z^{n+2}} \; dz.$$ Extrayendo el residuo encontramos $$\frac{1}{2^{n+1}} \sum_{q=0}^{n+1} {2n+3\choose q} = \frac{1}{2^{n+2}} \sum_{q=0}^{2n+3} {2n+3\choose q} = \frac{1}{2^{n+2}} 2^{2n+3} = 2^{n+1}.$$

Ahora el RHS es simplemente el doble del LHS con $n+1$ sustituido por $n$ por lo que obtenemos $$2\times 2^n = 2^{n+1}$$ y los dos son, en efecto, los mismos, como se afirma.

Aquí no hemos hecho uso de las propiedades de las integrales complejas por lo que este cálculo también se puede presentar utilizando sólo el álgebra de funciones generadoras.

Al parecer, este método se debe a Egorychev, aunque parte de él es probablemente folclore.