La identidad de las sumas de los coeficientes binomiales

Question

Estoy tratando de probar la siguiente: $$\sum_{k=0}^n 2^k\binom{2n-k}{n}=4^n$$

He pensado acerca de la inducción, pero no hay una manera muy agradable para cambiar el lado izquierdo de la $n$ de los casos a la $n+1$ caso multiplicando por $4$, al menos, ninguno que yo pueda ver.

También he pensado en intentar poner una combinatoria argumento juntos, de alguna manera, argumentando que la LHS cuenta $n$-letra de la palabra a partir de una $4$letras del alfabeto, pero no puedo conseguir el set de ser tomados en cuenta para la partición de una manera que con sensatez representa los diferentes términos de la suma.

Yo creo que la identidad es verdadera, no sólo porque yo he probado un par de pequeños valores de $n$, pero también porque Wolfram Alpha simplifica para mí. Simplemente no me diga cómo.

Gracias de antemano por cualquier perspectiva.

---

Contexto adicional: Esta identidad se levantó, mientras que el estudio de las respuestas a esta pregunta de probabilidad: número Esperado de sorteos para encontrar una coincidencia

Answer 1

Hay un bonito combinatoria prueba que involucran caminatas en el plano 2D.

Considere la posibilidad de $4^n$ como el conjunto de cadenas de $2n$ símbolos, cada uno de los cuales es $U$ o $R$, para los de "arriba" y "derecha". Esto determina un paseo en un 2D de celosía, a partir de a $(0,0)$ y terminando en algún punto de $(m,2n-m)$ algunos $0\le m \le 2n$.

Deje $S$ ser el siguiente conjunto de puntos: $$ S=\{(n,n-k):0\le k\le n\}\cup\{(n-k,n):0\le k\le n\} $$ Es decir, $S$ se compone de la red de puntos en la parte superior y el límite derecho de la plaza de la $[0,n]\times[0,n]$.

Cada pie debe finalmente golpeó $S$. Considerar el último punto en $S$ que el pie de visitas. Siempre que $k>1$, afirmo que el número de los paseos para que el último punto en $S$ que el golpe es $(n,n-k)$ es igual a $$ \binom{2n-k}{n}2^{k-1} $$ Es decir, como un paseo, es determinar por un camino de$(0,0)$$(n,n-k)$, el número de los cuales es $\binom{n+n-k}{n}$, seguido por un "derecho" de paso, seguido por ${k-1}$ arbitrarias pasos.

Combinando esto con los casos en los que la última vez que visitó punto está en el borde superior de la plaza, $(n-k,n)$, y en el caso de que el visitado el punto es $(n,n)$, su suma es alcanzado.