Cómo probar que $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$.

Question

Así he estado luchando con esta suma para rato y yo solo no puedo descubrirlo. He intentado probar por inducción que si la suma anterior es un $S_n$ $S_{n+1} = 4S_n$, pero no realmente tener éxito así que aquí estoy. Gracias de antemano.

Answer 1

Usamos la forma equivalente $$\sum_{k=n}^{2n}2^{-k}\binom{k}{n}=1$$ de @MotylaNogaTomkaMazura. Este se obtiene al notar que a $4^n=2^{2n}$ y ajuste de $k=2n-i$.

Con el fin de hacer más dinero, el Mundo de la Serie de normas que han sido modificadas, por lo que el primer equipo en ganar $n+1$ juegos gana la Serie. (Las reglas actuales tiene $n=3$.)

Deje $p_k$ la probabilidad de la Serie Mundial termina en $k+1$ los juegos, si cada equipo tiene probabilidad de $1/2$ de ganar a cualquier juego, y los resultados del juego son independientes.

La serie termina en $k+1$ juegos de precisión si una de las $2$ equipos de wins $n$ de la primera $k$ juegos y luego gana el próximo partido. Así $$p_k=2\binom{k}{n}(1/2)^{k}(1/2)=2^{-k}\binom{k}{n}.$$

Ahora se suman, $k=n$$2n$. Las probabilidades deben sumar a $1$.

Answer 2

Puedo dar una prueba suavemente fea por inducción. Deje que

$$S_n=\sum_{k=0}^n2^k\binom{2n-k}n=\sum_{k=0}^n2^k\binom{2n-k}{n-k}=\sum_{k=0}^n2^{n-k}\binom{n+k}n\;,$$

y asumir que $S_n=4^n=2^{2n}$. Entonces

$$\begin{align*} S_{n+1}&=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+1+k}{n+1}\\ &=\sum_{k=0}^{n+1}2^{n+1-k}\left(\binom{n+k}n+\binom{n+k}{n+1}\right)\\ &=\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}n+\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\ &=\binom{2n+1}n+2\sum_{k=0}^n2^{n-k}\binom{n+k}n+\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\ &=\binom{2n+1}n+2^{2n+1}+\sum_{k=1}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\ &=2^{2n+1}+\binom{2n+1}n+\binom{2n+1}{n+1}+\sum_{k=1}^n2^{n+1-k}\binom{n+k}{n+1}\\ &=2^{2n+1}+\binom{2n+2}{n+1}+\sum_{k=0}^{n-1}2^{n-k}\binom{n+1+k}{n+1}\\ &=2^{2n+1}+\binom{2n+2}{n+1}+\frac12\left(S_{n+1}-\binom{2n+2}{n+1}-2\binom{2n+1}{n+1}\right)\\ &=2^{2n+1}+\binom{2n+2}{n+1}+\frac12\left(S_{n+1}-2\binom{2n+2}{n+1}\right)\\ &=2^{2n+1}+\frac12S_{n+1}\;, \end{align*} $$

así $\frac12S_{n+1}=2^{2n+1}$ y $S_{n+1}=2^{2n+2}=4^{n+1}$.

Answer 3

Acaba de presentar de otra manera: $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,\,n} {\left( \matriz{ 2n - k \cr n \cr} \right)2^{\,k} } = \sum\limits_{0\, \le \,k\,\left( { \le \,\,n} \right)} {\left( \matriz{ 2n - k \cr n - k \cr} \right)2^{\,k} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,\,n} \right)} {\left( \matriz{ 2n - k \cr n - k \cr} \right)\left( {1 + 1} \right)^{\,k} } = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,\,n} \right)} {\sum\limits_{0\, \le \,k\,\left( { \le \,\,n} \right)} {\left( \matriz{ 2n - k \cr n - k \cr} \right)\left( \matriz{ k \cr j \cr} \right)} } = \cr & = \sum\limits_{0\, \le \,j\,\left( { \le \,\,n} \right)} {\sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,\,n} \right)} {\left( \matriz{ 2n - k \cr n - k \cr} \right)\left( \matriz{ k \cr k - j \cr} \right)} } = \cr & = \sum\limits_{0\, \le \,j\,\left( { \le \,\,n} \right)} {\left( \matriz{ 2n + 1 \cr n - j \cr} \right)} = \sum\limits_{0\, \le \,\,l\, \le \,\,n} {\left( \matriz{ 2n + 1 \cr l \cr} \right)} = {1 \over 2}\sum\limits_{0\, \le \,\,l\, \le \,\,2n + 1} {\left( \matriz{ 2n + 1 \cr l \cr} \right)} = \cr Y = 2^{\,2n} \cr} $$

Answer 4

Deriva esta solución pero sólo di cuenta que es un poco similar a uno publicado por taxi G arriba, pero aquí está de todos modos.

$$\begin{align} \sum_{i=0}^n \color{blue}{2^i}\binom{2n-i}n &=\sum_{i=0}^n\color{blue}{\sum_{j=0}^i\binom ij}\binom {2n-i}n\\ &=\sum_{j=0}^n\sum_{i=j}^n\binom i{i-j}\binom{2n-i}{n-i} &&\text{swapping indices and using symmetry}\\ &=\sum_{j=0}^n\sum_{i=j}^n(-1)^{i-j}\binom{-j-1}{i-j}(-1)^{n-i}\binom{-n-1}{n-i} &&\text{upper negation}\\ &=\sum_{j=0}^n(-1)^{n-j}\sum_{i=j}^n\binom {-j-1}{i-j}\binom{-n-1}{n-i}\\ &=\sum_{j=0}^n(-1)^{n-j}\binom{-n-j-2}{n-j} &&\text{Vandermonde Identity}\\ &=\sum_{j=0}^n(-1)^{n-j}(-1)^{n-j}\binom{2n+1}{n-j} &&\text{upper negation}\\ &=\sum_{j=0}^n\binom{2n+1}{n+1+j} &&\text{symmetry}\\ &=\sum_{k=n+1}^{2n+1}\binom{2n+1}k &&\text{putting %#%#%}\\ &=\frac 12 \sum_{k=0}^{2n+1}\binom{2n+1}k\\ &=\frac12\cdot 2^{2n+1}\\ &=4^n\qquad\blacksquare \end {Alinee el} $$

Answer 5

Combinatoria prueba: vamos a escribir $[n]$$\{1,2,\dots, n\}$, e $[n]^{(r)}$ para la colección de todos los $r$-tamaño de los subconjuntos de a $[n]$. Utilizamos el estándar $[i, j]$$\{i, i+1, \dots, j \}$.

Exponemos un bijection entre el $$\{ (i, s \subseteq [i], t \subseteq [i+1, 2n]^{(n-i)}) : i = 0, 1, \dots, n \}$$ y los subconjuntos de a $[2n]$.

Deja $$\begin{equation} \phi(i, s, t)= \begin{cases} ([i+1, 2n] \setminus t) \sqcup s, & \text{if}\ i \in s \\ t \sqcup s, & \text{if}\ i \not \in s \end{casos} \end{equation}$$ donde $\sqcup$ es una unión en la que hacemos hincapié en que los argumentos son distintos. En el primer caso, no se entre $n$ $n+i$ elementos de $\phi(i, s, t)$; en el segundo, hay entre $n-i$ $n$ elementos.

Pretendemos que $\phi$ es un bijection.

Lema: $\phi$ es inyectiva.

Prueba: si $\phi(i,s,t) = \phi(j,a,b)$ es suficiente para demostrar que $i=j$, debido a que, a continuación, $$s = [i] \cap \phi(i,s,t) = [j] \cap \phi(j,a,b) = a$ $ y:

• Si $i \in s$, $j \in a$ $$[i, 2n] \setminus t = [i, 2n] \cap \phi(i,s,t) = [j, 2n] \cap \phi(j,a,b) = [j, 2n] \setminus b$$
• Si $i \not \in s$, $j \not \in b$ $$t = [i, 2n] \cap \phi(i, s, t) = [j, 2n] \cap \phi(j, a, b) = b$$

Supongamos, entonces, de la contradicción, que $i \not = j$. Por simetría, wlog $i$ es el menor. Entonces tenemos una muy tedioso caso-bash que me temo que no va a pasar, pero llegamos a una contradicción.

Lema: $\phi$ es surjective.

La única manera que tengo de probar este es un muy largo y aburrido de la especificación de la matriz inversa de a $\phi$. Estoy seguro de que debe haber una mejor manera, pero no puedo encontrarlo.