I am currently trying to work through The Algorithm Design Manual on my own and happened to hit a roadblock. Below is the solution found on the wiki and I don't understand the last part or where it came from. Could someone explain it to me? Or better yet point me to an article or book that explains the properties of Summations? I can't seem to find this referenced anywhere. Thanks in advance for your help!
$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=j}^{i+j} \sum_{l=1}^{i+j-k}1$
$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=j}^{i+j} i+j-k$
$\sum_{k=j}^{i+j} i+j-k = \sum_{k=1}^i (k)$
Since
$\sum_{k=start}^{end} (end-k)= \sum_{k=1}^{end-start}(k)$
2026-05-14 19:34:02.1778787242
Algorithms and Summations
30 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
Let me write $s$ for $start$ and $e$ for $end$. Then $$\sum_{k=s}^e(e-k)=[e-s]+[e-(s+1)]+\cdots+[0]=(e-s)+(e-s-1)+\cdots+0$$ and $$\sum_{k=1}^{e-s}k=1+2+\cdots+(e-s)$$ and either way you're adding up all the numbers from $1$ (or from zero) to $e-s$.