Condensing a sum into simpler notation

Question

I learned some shortcuts for some sums in school like:

$$\sum_{i=n}^m i=\frac{(m-n+1)(m+n)}{2}$$

So 1+2+3+...+10 = 55. For another sum I found this shortcut on my own:

$$\sum_{i_2=1}^{m} \sum_{i_1=1}^{i_2} 1 = \sum_{i=1}^{m} i= \frac{m(m+1)}{2}$$

But for a similar looking sum:

$$\sum_{i_2=1}^{m} \sum_{i_1=1}^{i_2} i_1$$

I don't know how to condense this to a simpler function like I did for the other ones. How would this be rewritten? I'd like to find a pattern so I can find a general rule to condense as many sums as I want, like this:

$$\sum_{i_n=1}^{m} \sum_{i_{n-1}=1}^{i_n}...\sum_{i_1=1}^{i_2} i_1$$

Sometimes I end up doing sums like these in programming and I can definitely use a shortcut when I'm several sums deep and it starts to take a long time to manually iterate through each sum.

Answer 1

For the sum $$\sum_{i_2=1}^{m} \sum_{i_1=1}^{i_2} i_1$$ You can simplify this to $$\sum_{i_2=1}^{m} \frac{i_2(i_2+1)}{2}$$ $$\sum_{i_2=1}^{m} \frac{1}{2}i_2^2+\frac{1}{2}i_2$$ $$\frac{1}{2}\sum_{i_2=1}^{m} i_2^2+ \frac{1}{2}\sum_{i_2=1}^{m} \frac{1}{2}i_2$$ $$\frac{m(m+1)(2m+1)}{12}+ \frac{m(m+1)}{4}$$ $$\frac{m(m+1)(2m+1)+3m(m+1)}{12}$$ $$\frac{(m+1)(m(2m+1)+3m)}{12}$$ $$\frac{m(2m+4)(m+1)}{12}$$ $$\frac{m(m+1)(m+2)}{6}$$ The next summation (not going to show work in my answer) turns out to be $$\frac{m(m+1)(m+2)(m+3)}{24}$$ You can probably conjecture that the nth summation (considering $\frac{m(m+1)}{2}$ as the second) will be $$\frac{1}{n!}\prod_{i=0}^{n-1} (m+i)$$ Though I'm not sure how exactly to prove this. Maybe try induction?

Edit: This holds for $n=1$ through $6$ using Wolfram Alpha's summation calculator.

Edit: Okay! I have a proof! I'm going to prove the above conjecture using mathematical induction. I have already shown that the conjecture holds for the first two, so that part is out of the way. Our conjecture is that

$$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)$$

Assume that this statement is true for some $n_k$. Then we must prove that its truth for some $n_k$ implies its truth for $n_{k+1}$, or that if the above is true, then

$$\sum_{n_k=1}^{n_{k+1}} \sum_{n_{k-1}=1}^{n_k} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{(k+1)!}\prod_{i=0}^{k} (n_{k+1}+i)$$

Must also be true. This may at first seem like a scary problem to attack until we remember that we assumed that

$$\sum_{n_{k-1}=1}^{n_k} \sum_{n_{k-2}=1}^{n_{k-1}} ... \sum_{n_0=1}^{n_1} 1=\frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)$$

was true, allowing us to substitute and instead have the task of proving

$$\sum_{n_k=1}^{n_{k+1}} \frac{1}{k!}\prod_{i=0}^{k-1} (n_k+i)=\frac{1}{(k+1)!}\prod_{i=0}^{k} (n_{k+1}+i)$$

Which is less intimidating. First one must notice that the quantity

$$\prod_{i=0}^{k-1} (n_k+i)$$

is equal to

$$\frac{(n_k+k-1)!}{(n_k-1)!}$$

and we can substitute this into our equation to get

$$\sum_{n_k=1}^{n_{k+1}} \frac{1}{k!}\frac{(n_k+k-1)!}{(n_k-1)!}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$

We can now notice that

$$\frac{1}{k!}\frac{(n_k+k-1)!}{(n_k-1)!}$$

is the same as

$$_{n_k+k-1}C_{n_k-1}$$

and so now we have

$$\sum_{n_k=1}^{n_{k+1}} {_{n_k+k-1}C_{n_k-1}}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$

Now we can attack the sum

$$\sum_{n_k=1}^{n_{k+1}} {_{n_k+k-1}C_{n_k-1}}$$

Which expands out to form

$$_kC_0+_{k+1}C_1+_{k+2}C_2+...+_{n_{k+1}+k-1}C_{n_{k+1}-1}$$

Now we can use the identity of the combinations formula (you can verify this identity for yourself)

$$_nC_r=_{n+1}C_r-_nC_{r-1}$$

to expand out our infinite sum:

$$_kC_0+(_{k+2}C_1-_{k+1}C_0)+(_{k+3}C_2-_{k+2}C_3)+...+(_{n_{k+1}+k}C_{n_{k+1}-1}-_{n_{k+1}+k-1}C_{n_{k+1}-2})$$

We can see now that this is a telescoping sum that condenses down to

$$_kC_0-_{k+1}C_0+_{n_{k+1}+k}C_{n_{k+1}-1}$$ $$=1-1+_{n_{k+1}+k}C_{n_{k+1}-1}$$ $$=_{n_{k+1}+k}C_{n_{k+1}-1}$$

When we substitute this into our equation, we get this:

$$_{n_{k+1}+k}C_{n_{k+1}-1}=\frac{1}{(k+1)!}\frac{(n_{k+1}+k)!}{(n_{k+1}-1)!}$$ $$\frac{(n_{k+1}+k)!}{(k+1)!(n_{k+1}-1)!}=\frac{(n_{k+1}+k)!}{(k+1)!(n_{k+1}-1)!}$$

Which is a truth statement. This proves that if our statement is true for some $k$, then is must be true for $k+1$, and since it is true for $k=1$, it is true for all natural numbers $k$. QED.

Answer 2

Why wouldn't you have the following $$ \sum_{j=1}^m \sum_{i=1}^ji = \sum_{j=1}^m \frac{j(j+1)}{2} = \frac{1}{2}\left(\frac{m(m+1)(2m+1)}{6}+\frac{m(m+1)}{2}\right)\ \ ? $$

The same technique could be extended by applying sum formulas for sequences of higher powers.

Answer 3

Using the Hockey-stick identity, we have

$$\begin{align} \sum_{i_1=1}^{i_2}i_1 &&=\binom {i_2+1}2\\ \sum_{i_2=1}^{i_3}\sum_{i_1=1}^{i_1}i_1&=\sum_{i_2=1}^{i_3}\binom {i_2+1}2 &=\binom {i_3+2}{3}\\ &\vdots\\ \sum_{i_n=1}^m\sum_{i_{n-1}}^{i_n}\cdots \sum_{i_2=1}^{i_3}\sum_{i_1=1}^{i_2}i_1&=\sum_{i_n=1}^m\binom {i_n+n-1}n&=\color{red}{\binom {m+n}{n+1}} \end{align}$$