Simplification of Nested Summations
Given the following code:
for i = 1 to n for j = 1 to i for k = j to (i+j) r = r + 1 end end
end
print rI get:
$$ \sum_{i=1}^n\left(\sum_{j=1}^i\left(\sum_{k=j}^{i+j}1\right)\right) = \frac{1}{3}n(n+1)(n+2) $$
using wolfram alpha, I can get to the left hand side but have no idea how to reach the function of n by myself. I really need to learn this but I don't even know what the process is called! Any pointers on where to learn the method would be appreciated.
$\endgroup$ 02 Answers
$\begingroup$Hint
Start from the inside and continue. The result of the most inside summation is just ($1+i$) which now you have to sum from $j=1$ to $j=i$. So, the result of the middle summation is $i(i+1)$ which is the sum of numbers plus the sum of their squares. So, you should end with the formula.
I am sure that you can take from here.
$\endgroup$ 3 $\begingroup$We can use the identity $$ \sum_{j=k}^n\binom{j}{k}=\binom{n+1}{k+1}\tag{1} $$ which is proven in the answers to this question.
Then compute
$$
\begin{align}
\sum_{i=1}^n\sum_{j=1}^i\sum_{k=j}^{i+j}1
&=\sum_{i=1}^n\sum_{j=1}^ii+1\tag{2}\\
&=\sum_{i=1}^ni(i+1)\tag{3}\\
&=\sum_{i=1}^n2\binom{i+1}{2}\tag{4}\\
&=\sum_{i=2}^{n+1}2\binom{i}{2}\tag{5}\\
&=2\binom{n+2}{3}\tag{6}\\
&=\frac{(n+2)(n+1)n}{3}\tag{7}
\end{align}
$$
Explanation:
$(2)$: summing $i+1$ terms of $1$
$(3)$: summing $i$ terms of $i+1$
$(4)$: value of binomial coefficient
$(5)$: substitution $i\mapsto i-1$
$(6)$: apply $(1)$
$(7)$: value of binomial coefficient
Another Proof of $\mathbf{(1)}$:
The recursion that defines Pascal's Triangle is
$$
\binom{j+1}{k+1}=\binom{j}{k}+\binom{j}{k+1}\tag{8}
$$
Thus, we can write
$$
\begin{align}
\sum_{j=k}^n\binom{j}{k}
&=\sum_{j=k}^n\left[\binom{j+1}{k+1}-\binom{j}{k+1}\right]\tag{9}\\
&=\sum_{j=k+1}^{n+1}\binom{j}{k+1}-\sum_{j=k}^n\binom{j}{k+1}\tag{10}\\
&=\left(\binom{n+1}{k+1}+\color{#C00000}{\sum_{j=k+1}^n\binom{j}{k+1}}\right)
-\left(\binom{k}{k+1}+\color{#C00000}{\sum_{j=k+1}^n\binom{j}{k+1}}\right)\tag{11}\\
&=\binom{n+1}{k+1}-\binom{k}{k+1}\tag{12}\\
&=\binom{n+1}{k+1}\tag{13}
\end{align}
$$
Explanation:
$\ \:(9)$: Apply $(8)$
$(10)$: split the sum into two and reindex the first ($j\mapsto j-1$)
$(11)$: pull the $j=n+1$ term out of the first sum and the $j=k$ term out of the second
$(12)$: cancel identical sums
$(13)$: $\binom{k}{k+1}=0$
