Prueba de la identidad $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$

Question

Acabo de encontrar esta identidad pero sin ninguna prueba, ¿podríais darme una pista de cómo podría probarla? $$2^n = \sum\limits_{k=0}^n 2^{-k} \cdot \binom{n+k}{k}$$

Sé que $$2^n = \sum\limits_{k=0}^n \binom{n}{k}$$ pero eso no me ayudó

Answer 1

Hagámoslo de forma perezosa, en flujo de conciencia, ajustando pequeños detalles uno a uno hasta que parezca una enumeración reconocible.

Primero combinarlo multiplicando todo por $2^n$ , a

$$2^{2n} = \sum\limits_{k=0}^n 2^{n-k} \cdot \binom{n+k}{k}$$

Esto se ve mejor, porque $(n-k)$ y $(n+k)$ parece una descomposición de $2n$ . El lado izquierdo cuenta todos los subconjuntos de un $2n$ conjunto de elementos, así que tal vez algo sobre el subconjunto mayor y menor en la partición de $2n$ elementos en un subconjunto y su complemento. Algún sentimiento difuso sobre la necesidad de romper la simetría cuando los conjuntos son de igual tamaño dice multiplicar por $2$ y considerar subconjuntos de a $2n+1$ conjunto de elementos, que como partición del conjunto tiene una parte mayor y otra menor. Por lo tanto,

$$2^{2n+1} = \sum\limits_{k=0}^n 2 \times 2^{n-k} \cdot \binom{n+k}{k}$$ o

$$2^{2n+1} = \sum\limits_{k=0}^n 2 \times 2^{n-k} \cdot \binom{n+k}{n}$$

¡Mejor! Un subconjunto de un tamaño $2n+1$ es equivalente a una partición en (un conjunto mayor con más de $n$ elementos) $\cup$ (conjunto más pequeño con menos de $n$ ), y una elección (el $\times 2$ ) de los cuales uno es el subconjunto. Y podemos elegir el subconjunto mayor seleccionando primero su mayor $n+1$ y, a continuación, añadir un subconjunto aleatorio de los elementos de índice inferior (esto es el $2^{n-k}$ ), y... vale, ya está todo claro:

Desde la primera $2n+1$ enteros, seleccione un subconjunto dividiéndolo en un subconjunto grande y otro pequeño y escogiendo ( $\times 2$ ) uno de ellos como el conjunto. Determinar el subconjunto grande, que tiene al menos $n+1$ elementos, seleccionando un índice $j$ de $1$ a $n+1$ como la ubicación del $(n+1)$ elemento más grande del conjunto, seleccionando el $n$ elementos anteriores $j$ (hay ${2n+1 - j} \choose {n}$ opciones) y añadiendo cualquier subconjunto de los elementos siguientes $j$ (hay $2^{j-1}$ de los mismos). Esta es la última suma con $k = n+1 - j$ .

En sentido contrario, dividir por $2^n$ para conseguir

$$1 = \sum\limits_{k=0}^n 2^{-(n+k)} \cdot \binom{n+k}{n}$$

y buscar un proceso de probabilidad natural que proporcione esta distribución. Una respuesta:

Lanza una moneda para determinar si los votantes $1, 2, \ldots$ apoyan al candidato $A$ o $B$ en una elección, y detener el proceso cuando uno de los candidatos alcance $n+1$ votos. La detención se produce en un momento dado $t$ entre $n+1$ y $2n+1$ pasos, y si $k=t-1-n$ el conjunto de momentos en los que el candidato vencedor recibió votos antes del tiempo $t$ es uno de ${{t-1} \choose n} = {{n+k} \choose n}$ posibilidades.

Creo que este proceso es esencialmente lo mismo que lo que a veces se llama el problema de la caja de cerillas de Banach.

Answer 2

Se puede demostrar por inducción en $n$ . He aquí un comienzo. Deja que

$$f(n)=\sum_{k=0}^n2^{-k}\binom{n+k}k\;;$$

claramente $f(0)=1=2^0$ . Supongamos que $f(n)=2^n$ para algunos $n\ge 0$ . Entonces

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

y

$$f(n+1)=2^{-(n+1)}\binom{2n+2}{n+1}+\sum_{k=0}^n2^{-k}\binom{n+1+k}k\;.$$

Ahora combina estos resultados y utiliza el hecho de que

$$\binom{2n+2}{n+1}=\binom{2n+1}{n+1}+\binom{2n+1}n=2\binom{2n+1}n$$

para completar el paso de inducción.

Answer 3

Traté de generalizar, pero la ecuación $(2)$ muestra por qué $x=\frac12$ es necesario para hacer una ecuación simple.

Tenga en cuenta que $$ \begin{align} \sum_{k=0}^{n+1}x^k\binom{n+k+1}{k} &=\sum_{k=0}^{n+1}x^k\left[\binom{n+k}{k}+\binom{n+k}{k-1}\right]\\ &=\sum_{k=0}^nx^k\binom{n+k}{k}+x^{n+1}\binom{2n+1}{n+1}\\ &+\sum_{k=0}^{n+1}x^{k+1}\binom{n+k+1}{k}-x^{n+2}\binom{2n+2}{n+1}\tag{1} \end{align} $$ Desplazar los términos y multiplicar por $(1-x)^n$ tenemos $$ \begin{align} \hspace{-1cm}(1-x)^{n+1}\sum_{k=0}^{n+1}x^k\binom{n+k+1}{k} &=(1-x)^n\sum_{k=0}^nx^k\binom{n+k}{k}\\ &+(1-x)^n\left[x^{n+1}\binom{2n+1}{n}-x^{n+2}\binom{2n+2}{n+1}\right]\\ &=(1-x)^n\sum_{k=0}^nx^k\binom{n+k}{k}\\ &+(1-x)^n\left[\frac12x^{n+1}-x^{n+2}\right]\binom{2n+2}{n+1}\tag{2} \end{align} $$ desde $\binom{2n+1}{n+1}=\binom{2n+1}{n}$ y $\binom{2n+1}{n+1}+\binom{2n+1}{n}=\binom{2n+2}{n+1}$ .

Configuración $x=\frac12$ en $(2)$ produce $$ \begin{align} 2^{-n-1}\sum_{k=0}^{n+1}2^{-k}\binom{n+k+1}{k} &=2^{-n}\sum_{k=0}^n2^{-k}\binom{n+k}{k}\\ &\vdots\\ &=2^{-0}\sum_{k=0}^02^{-k}\binom{0+k}{k}\\[9pt] &=1\tag{3} \end{align} $$ Por lo tanto, $$ \sum_{k=0}^n2^{-k}\binom{n+k}{k}=2^n\tag{4} $$

Answer 4

Supongamos que buscamos verificar que

$$S_n = \sum_{k=0}^n 2^{-k} {n+k\choose k} = 2^n.$$

Introducimos el soporte Iverson

$$[[0\le k\le n]] = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n-k+1}} \frac{1}{1-z} \; dz$$

por lo que podemos ampliar $k$ hasta el infinito, obteniendo

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \sum_{k\ge 0} 2^{-k} {n+k\choose n} z^k \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \frac{1}{(1-z/2)^{n+1}} \; dz.$$

Lo evaluamos utilizando el negativo de los residuos en $z=1, z=2$ y $z=\infty.$ Obtenemos para el residuo en $z=1$

$$- \frac{1}{(1/2)^{n+1}} = - 2^{n+1}.$$

Para el residuo en $z=2$ escribimos

$$\frac{(-1)^{n+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \frac{1}{(z/2-1)^{n+1}} \; dz \\ = \frac{(-1)^{n+1} \times 2^{n+1}}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{1}{1-z} \frac{1}{(z-2)^{n+1}} \; dz $$

y requerimos la derivada

$$\frac{1}{n!} \left(\frac{1}{z^{n+1}} \frac{1}{1-z}\right)^{(n)} \\ = \frac{1}{n!} \sum_{q=0}^n {n\choose q} (-1)^q \frac{(n+q)!}{n!} \frac{1}{z^{n+1+q}} \frac{(n-q)!}{(1-z)^{n-q+1}}.$$

Esto se simplifica a

$$\sum_{q=0}^n \frac{n!}{q! (n-q)!} \frac{1}{n!} \frac{(n+q)! (n-q)!}{n!} (-1)^q \frac{1}{z^{n+1+q}} \frac{1}{(1-z)^{n-q+1}} \\ = \sum_{q=0}^n {n+q\choose q} (-1)^q \frac{1}{z^{n+1+q}} \frac{1}{(1-z)^{n-q+1}}.$$

Evaluar en $z=2$ para conseguir

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

Por lo tanto, el residuo en $z=2$ contribuye

$$\sum_{q=0}^n 2^{-q} {n+q\choose q} = S_n.$$

Finalmente hacer el residuo en $z=\infty$

$$\mathrm{Res}_{z=\infty} \frac{1}{z^{n+1}} \frac{1}{1-z} \frac{1}{(1-z/2)^{n+1}} \\ = - \mathrm{Res}_{z=0} \frac{1}{z^2} z^{n+1} \frac{1}{1-1/z} \frac{1}{(1-1/2/z)^{n+1}} \\ = - \mathrm{Res}_{z=0} \frac{1}{z} z^{n+1} \frac{1}{z-1} \frac{z^{n+1}}{(z-1/2)^{n+1}} \\ = - \mathrm{Res}_{z=0} z^{2n+1} \frac{1}{z-1} \frac{1}{(z-1/2)^{n+1}} = 0.$$

Utilizando el hecho de que los residuos suman cero, obtenemos

$$S_n - 2^{n+1} + S_n = 0$$

que da como resultado

$$\bbox[5px,border:2px solid #00A000]{ S_n = 2^n.}$$

Answer 5

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{2^n = \sum_{k = 0}^{n}2^{-k}{n + k \choose k}:\ {\large ?}}$

$\ds{\tt\mbox{The following method is a straightforward one}}$ .

En adelante utilizaremos la identidad $$\begin{array}{|c|}\hline\\ \ds{\quad{\,m \choose \ell\,}=\oint_{\verts{z}\ =\ b\ >\ 0} {\pars{1 + z}^{m} \over z^{\ell + 1}}\,{\dd z \over 2\pi\ic}\quad} \\ \\ \hline \end{array} $$

\begin {align}& \color {#66f}{ \large\sum_ {k = 0}^{n}2^{-k}{n + k \choose k}} = \sum_ {k = - \infty }^{n}2^{-k}{n + k \choose n} = \sum_ {k = \infty }^{-n}2^{k}{n - k \choose n} = \sum_ {k = \infty }^{0}2^{k - n}{2n - k \choose n} \\ [5mm]&=2^{-n} \sum_ {k = 0}^{ \infty }2^{k}{2n - k \choose n} =2^{-n} \sum_ {k = 0}^{ \infty }2^{k} \oint_ { \verts {z}\ =\ a\ >\ 1} { \pars {1 + z}^{2n - k} \over z^{n + 1}} \,{ \dd z \over 2 \pi\ic } \\ [5mm]&=2^{-n} \oint_ { \verts {z}\ =\ a\ >\ 1}{ \pars {1 + z}^{2n} \over z^{n + 1}} \sum_ {k = 0}^{ \infty } \pars {2 \over 1 + z}^{k}\N-, { \dd z \over 2 \pi\ic } \\ [5mm]&=2^{-n} \oint_ { \verts {z}\ =\ a\ >\ 1}{ \pars {1 + z}^{2n} \over z^{n + 1}} {1 \over 1 - 2/ \pars {1 + z}}\,{ \dd z \over 2 \pi\ic } =2^{-n} \oint_ { \verts {z}\ =\ a\ >\ 1} { \pars {1 + z}^{2n + 1} \over z^{n + 1} \pars {z - 1}}\,{ \dd z \over 2 \pi\ic } \\ [5mm]&=2^{-n} \sum_ {k = 0}^{ \infty } \oint_ { \verts {z}\ =\ a\ >\ 1}{ \pars {1 + z}^{2n + 1} \over z^{n + 2 + k}\},{ \dd z \over 2 \pi\ic } =2^{-n} \sum_ {k = 0}^{ \infty }{2n + 1 \choose n + k + 1} \end {align}

$$ \mbox{Then,}\quad\color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k}} =2^{-n}\color{#c00000}{\sum_{k = 0}^{n}{2n + 1 \choose n - k}}\tag{1} $$

El $\ds{\color{#c00000}{\mbox{"red expression"}}}$ en $\pars{1}$ se convierte: \begin {align} & \color {#c00000}{ \sum_ {k = 0}^{n}{2n + 1 \choose n - k}} = \sum_ {k = 0}^{-n}{2n + 1 \choose n + k} = \sum_ {k = n}^{0}{2n + 1 \choose k} = \sum_ {k = 0}^{2n + 1}{2n + 1 \choose k} - \sum_ {k = n + 1}^{2n + 1}{2n + 1 \choose k} \\ [3mm]&=2^{2n + 1} - \sum_ {k = 0}^{n}{2n + 1 \choose k + n + 1} =2^{2n + 1} - \color {#c00000}{ \sum_ {k = 0}^{n}{2n + 1 \choose n - k}\a} \imp\ \begin {array}{|c|} \hline\\ \quad\color {#c00000}{ \sum_ {k = 0}^{n}{2n + 1 \choose n - k}} = 2^{2n} \quad \\ \\ \hline \end {array} \end {align}

Reemplazamos este resultado en la expresión $\pars{1}$ : $$ \color{#66f}{\large\sum_{k = 0}^{n}2^{-k}{n + k \choose k} = 2^{n}} $$