Suma de la suma de coeficientes binomiales $\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$

Question

Sé que no hay una manera sencilla de resolver la suma:

$$\sum_{k=0}^{j}{{n}\choose{k}}$$

Pero ¿qué hay de la ecuación:

$$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$

¿Existen simplificaciones o buenas aproximaciones para esta ecuación?

Answer 1

Básicamente, se trata simplemente de revertir el orden de la suma, al igual que podría revertir el orden de integración de una integral doble, aunque el límite inferior de $1$ en la suma externa requiere un pequeño ajuste.

$$\begin{align*} \sum_{j=1}^n\sum_{k=0}^j\binom{n}k&=\sum_{j=0}^n\sum_{k=0}^j\binom{n}k-\binom{n}0\\ &=\sum_{k=0}^n\sum_{j=k}^n\binom{n}k-1\\ &=\sum_{k=0}^n(n-k+1)\binom{n}k-1\\ &=(n+1)\sum_{k=0}^n\binom{n}k-\sum_{k=0}^nk\binom{n}k-1\\ &=(n+1)2^n-\sum_{k=0}^nn\binom{n-1}{k-1}-1\\ &=(n+1)2^n-1-n\sum_{k=0}^{n-1}\binom{n-1}k\\ &=(n+1)2^n-1-n2^{n-1}\\ &=(n+2)2^{n-1}-1 \end{align*}$$

Answer 2

Vamos a ver.

$\begin{array}\\ s(n) &=\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}\\ &=-1+\sum_{j=0}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}\\ &=-1+\sum_{k=0}^{n}\sum_{j=k}^{n}{{n}\choose{k}}\\ &=-1+\sum_{k=0}^{n}(n-k+1){{n}\choose{k}}\\ &=-1+\sum_{k=0}^{n}(n+1){{n}\choose{k}}-\sum_{k=0}^{n}k{{n}\choose{k}}\\ &=-1+(n+1)2^n-\sum_{k=0}^{n}k\dfrac{n!}{k!(n-k)!}\\ &=-1+(n+1)2^n-\sum_{k=1}^{n}\dfrac{n!}{(k-1)!(n-k)!}\\ &=-1+(n+1)2^n-n\sum_{k=1}^{n}\dfrac{(n-1)!}{(k-1)!(n-k)!}\\ &=-1+(n+1)2^n-n\sum_{k=1}^{n}\binom{n-1}{k-1}\\ &=-1+(n+1)2^n-n\sum_{k=0}^{n-1}\binom{n-1}{k}\\ &=-1+(n+1)2^n-n2^{n-1}\\ &=-1+2^{n-1}(2(n+1)-n)\\ &=-1+2^{n-1}(n+2)\\ \end{array} $

Una sorpresa agradable.

Answer 3

Hay. Comienza a reescribir la doble suma como $$\begin{align} \sum_{j=1}^n \sum_{k=0}^j \binom{n}{k} &= \sum_{j=1}^n \sum_{k=0}^n \binom{n}{k} \mathbb{1}_{k\leq j} = \sum_{k=0}^n \sum_{j=1}^n \binom{n}{k} \mathbb{1}_{k\leq j} = \sum_{k=0}^n \sum_{j=k}^n \binom{n}{k} - 1 = \sum_{k=0}^n \binom{n}{k} \sum_{j=k}^n 1 = 1 \\ &= \sum_{k=0}^n \binom{n}{k} (n-k+1) -1 = (n+1)\sum_{k=0}^n \binom{n}{k} - \sum_{k=0}^n k \binom{n}{k} -1 \end{align}$$ Ahora, esto se vuelve fácil de calcular -- ambas sumas tienen formas cerradas.

Answer 4

$$\begin{align} \sum_{j=\color{red}0}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}} &=\sum_{k=0}^n\sum_{j=k}^n\binom nk\\ &=\sum_{k=0}^n (n-k+1)\binom n{n-k}\\ &=\sum_{k=0}^n (j+1)\binom nj &&\text{poniendo }j=n-k\\ &=\sum_{k=0}^n j\binom nj+\sum_{k=0}^n \binom nj\\ &=n 2^{n-1}+2^n\\ \sum_{j=\color{red}1}^n\sum_{k=0}^n\binom nk&=\sum_{j=\color{red}0}^n\sum_{k=0}^n\binom nk-1\\ &=n 2^{n-1}+2^n-1\\ &=(n+2)2^{n-1}-1\quad\blacksquare \end{align}$$