Sé que no hay manera simple de resolver la suma:
$$\sum_{k=0}^{j}{{n}\choose{k}}$$
Pero, ¿qué acerca de la ecuación:
$$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$
Hay simplificaciones o buenas aproximaciones para esta ecuación?
Respuestas
¿Demasiados anuncios?
Básicamente es sólo una cuestión de invertir el orden de la suma, tanto como se podría invertir el orden de integración de una integral doble, a pesar de que el límite inferior de $1$ en el exterior de la suma requiere un poco de 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*}$$
marty cohen
Puntos
33863
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 agradable sorpresa.
Clement C.
Puntos
16603
Hay. Inicio de la reescritura de 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 convierte en fácil de calcular -- ambas sumas se han cerrado las formas.
martinhans
Puntos
131
$$\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{putting }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}$$
