I am working through the Algorithm Design Manual. Chapter 2 Problem 2 has us evaluate the return value of a function which consists of three nested loops which can be expressed by the following triply nested summation:
$$
\sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=j}^{i+j} 1
$$
I get stuck on the very first step of evaluating the outermost summation:
$$
\sum_{i=1}^{n} \sum_{j=1}^{i} \sum_{k=j}^{i+j} 1 = \sum_{i=1}^{n} \sum_{j=1}^{i}(??)
$$
Best Answer
The innermost summation has the form $$ \sum_{k=\rm start}^{\rm finish} 1 $$ You are counting the value $1$ starting at $k={\rm start}$ and ending at $k={\rm finish}$, which means you're counting $${\rm finish} - {\rm start} + 1$$ copies. Note the extra $1$; the answer is not simply ${\rm finish} - {\rm start}$. Check that this general formula works when finish = start, or when start = $1$.
So in your context the value of (??) is $$(i+j)-(j) + 1 = i+1.$$