Suma finita doble $\sum_{j=0}^n\sum_{i=0}^j \binom {n+1}{j+1}\binom ni =2^{2n}$

Question

El problema se da en una hoja de estudio de clase de combinatoria. No puedo demostrar, y realmente no estoy seguro si hubo un error en la pregunta o no. Trataba de unos pequeños eñes por ejemplo 1, 2 y se lleva a cabo. $\\$
Necesito demostrar que $\\$ $\mathop{\sum_{j=0}^{n}\sum_{i=0}^{j}}$ $n+1 \choose j+1$ $n \choose i $ = $2^{2n}$ $\forall n$ $\in$ $\mathbb{Z}^{+}$

Answer 1

Damos un probabilística de la interpretación. Cambiando de probabilidades a cuenta, tenemos una combinatoria de interpretación.

Alicia lanza una moneda no trucada $n+1$ a veces, y Beti lanza una moneda no trucada $n$ veces. Alicia gana si ella tiene más cabezas de Beti.

Nuestros suma doble, dividido por $2^{2n+1}$, da la probabilidad de que Alicia gana. Vamos a mostrar que esta probabilidad es $\frac{1}{2}$. Luego multiplicando por $2^{2n+1}$ rendimientos nuestro resultado deseado.

Imagina que los dos jugadores de cada lanzamiento de sus monedas simultáneamente $n$ veces. Si Alicia es líder después de $n$ lanzamientos, ella va a ganar. Si Beti es líder después de $n$ tiros, luego Beti va a ganar. Por la simetría de estos dos eventos son igualmente probables.

Y si están empatados después de $n$ tiros, a continuación, con una probabilidad de $\frac{1}{2}$, Alicia va a obtener una ventaja en el $(n+1)$-ésimo lanzamiento, y ganar. Y con una probabilidad de $\frac{1}{2}$ ella recibirá una cola y perder.

Answer 2

La identidad como se indica en la pregunta es correcta.

$$\begin{align} \sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni &=\sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom n{n-i}\\ &=\sum_{j=0}^n\sum_{r=0}^j\binom {n+1}{j+1}\binom n{n+r-j} &&\text{(putting }r=j-i)\\ &=\sum_{r=0}^n\sum_{j=r}^n\binom {n+1}{j+1}\binom n{n+r-j} &&\text{(swapping order of indices)(}0\le r\le j\le n )\\ &=\sum_{r=0}^n\binom {2n+1}{n+1+r} &&\text{(Vandermonde)}\\ &\color{lightgrey}{=\frac 12 \sum_{r=0}^n\binom {2n+1}{n-r}+\binom {2n+1}{n+1+r}}\\ &\color{lightgrey}{=\frac 12 \sum_{r=0}^{2n+1} \binom {2n+1}r}\\ &=\frac 12 \cdot 2^{2n+1}\\ &=2^{2n}\qquad\blacksquare\end {Alinee el} $$

---

Otro enfoque:

$$\begin{align} \sum_{j=0}^n\sum_{i=0}^j\binom {n+1}{j+1}\binom ni &=\sum_{j=0}^n\sum_{i=0}^j \left[\binom nj+\binom n{j+1}\right]\binom ni\\ &=\underbrace{\sum_{\large 0\le i\color{red}\le j\le n}\binom nj\binom ni}_*+\binom n{j+1}\binom ni\\ &=\overbrace{\sum_{\large 0\le i\color{red}= j\le n}\binom nj\binom ni+\sum_{\large 0\le i\color{red}<j\le n}\binom nj\binom ni}^*+\sum_{\large 0\le i\color{red}< j\le n}\binom nj\binom ni\\ &=\sum_{\large 0\le i\color{red}=j\le n}\binom nj\binom ni+2\sum_{\large 0\le i\color{red}< j\le n}\binom nj\binom ni\\ &=\sum_{\large 0\le i\color{red}=j\le n}\binom nj\binom ni+\sum_{\large 0\le i\color{red}\neq j\le n}\binom nj\binom ni&&\text{(by symmetry)}\\ &=\sum_{j=0}^n\sum_{i=0}^n\binom nj\binom ni&&\text{(**)}\\ &=\sum_{j=0}^n\binom nj\sum_{i=0}^n\binom ni\\\\ &=2^n\cdot 2^n\\\\ &=2^{2n}\qquad\blacksquare \end {Alinee el} $$

** como señala Alex en un Comentario sobre la pregunta original!

Answer 3

Aquí es otra variación del tema se basa en dos observaciones.

La primera observación es el cálculo de la doble suma de la región entera $$0\leq i,j\leq n$$ es simple.

\begin{align*} \sum_{j=0}^n\sum_{i=0}^{n}&\binom{n+1}{j+1}\binom{n}{i}\\ &=\sum_{j=1}^{n+1}\binom{n+1}{j}\sum_{i=0}^{n}\binom{n}{i}\tag{1}\\ &=\left(2^{n+1}-1\right)2^n\\ &=2\cdot4^n-2^n \end{align*}

Comentario:

• En (1) nos reorganizar el doble de la suma y cambio el índice de $j$ por uno.

La segunda observación se basa en la simetría. Se podría esperar que en la expresión de la suma doble con el triángulo superior $$0\leq j < i\leq n$$ as index range is very similar to the expression with the lower triangle $$0\leq i\leq j \leq n$$ como el rango del índice. De hecho, obtenemos \begin{align*} \sum_{j=0}^{n}&\sum_{i=j+1}^n\binom{n+1}{j+1}\binom{n}{i}\\ &=\sum_{j=0}^{n}\sum_{i=n-j+1}^n\binom{n+1}{n-j+1}\binom{n}{i}\tag{2}\\ &=\sum_{j=0}^{n}\sum_{i=0}^{j-1}\binom{n+1}{n-j+1}\binom{n}{i+n-j+1}\tag{3}\\ &=\sum_{j=1}^{n}\sum_{i=0}^{j-1}\binom{n+1}{j}\binom{n}{i}\tag{4}\\ &=\sum_{j=0}^{n-1}\sum_{i=0}^{j}\binom{n+1}{j+1}\binom{n}{i}\tag{5}\\ &=\sum_{j=0}^{n}\sum_{i=0}^{j}\binom{n+1}{j+1}\binom{n}{i}-2^n\tag{6}\\ \end{align*}

Comentario:

• En (2) reemplazamos $j\rightarrow n-j$

• En (3) se cambio el índice de $i$ a inicio de $0$

• En (4) utilizamos $\binom{n}{k}=\binom{n}{n-k}$ y sustituimos $i\rightarrow j-1-i$. Tomamos nota también de que el $j$ comienza con $j=1$ debido a la parte superior del índice de $i$ igual a $j-1$.

• En (5) se cambio el índice de $j$ por uno.

• En (6) añadimos $j=n$ a el doble de la suma y la resta $2^n$ respectivamente.

Vamos a ver, el doble de la suma con el triángulo superior como intervalo de índice puede ser transformado a la suma doble con el triángulo inferior, como índice de la gama. Poniendo todo junto obtenemos

\begin{align*} \sum_{j=0}^n&\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}+ \sum_{j=0}^n\sum_{i=j+1}^n\binom{n+1}{j+1}\binom{n}{i}\\ &=2\sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}-2^n \end{align*}

Obtenemos con (1)

\begin{align*} 2\sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}-2^n&=2\cdot 4^n-2^n\\ \end{align*}

resp.

\begin{align*} \sum_{j=0}^n\sum_{i=0}^j\binom{n+1}{j+1}\binom{n}{i}&=4^n\\ \end{align*}

y el reclamo de la siguiente manera.