5
$\begingroup$

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 r

I 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$
0
3
$\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$ I had got the inner most as being (1+i), hopefully correctly, from: (i+j+1-j). I'd also got that this needed to happen i times, and had multiplied out i(i+1) to get i²+i. I still don't know where to go next though, how does one get rid of the i? $\endgroup$ – Charlie Egan Feb 21 '14 at 11:49
  • $\begingroup$ You have to take the sum of the $i$'s and the sum of the $i^2$'s. $\endgroup$ – Claude Leibovici Feb 21 '14 at 11:54
  • $\begingroup$ Okay so I need to substitute this: upload.wikimedia.org/math/d/6/0/… for i². And this: upload.wikimedia.org/math/1/0/4/… for i. I didn't know about either of those equations. Then I need to simplify it down which I think I can do. $\endgroup$ – Charlie Egan Feb 21 '14 at 12:52
2
$\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$

$\endgroup$
10
  • $\begingroup$ Thanks for taking the time. My level of maths isn't great and I don't really understand some of the steps here, namely lines 3-5. The process described in the comments of Claude Leibovici's answer seem to make more intuitive sense to me. Thanks again for taking the time. $\endgroup$ – Charlie Egan Feb 21 '14 at 12:58
  • $\begingroup$ @CharlieEgan: If you are familiar with the binomial coefficients, $\binom{n}{2}=\frac{n(n-1)}{2}$ and $\binom{n}{3}=\frac{n(n-1)(n-2)}{6}$. The other step is a change of variables from $i$ to $i-1$ which moves the limits of summation up $1$. $\endgroup$ – robjohn Feb 21 '14 at 15:40
  • $\begingroup$ I know the formula for combinations, but evidently not well enough to understand your answer, sorry :( $\endgroup$ – Charlie Egan Feb 21 '14 at 19:13
  • $\begingroup$ @CharlieEgan: I have added a more detailed explanation. I hope that helps. $\endgroup$ – robjohn Feb 22 '14 at 1:06
  • $\begingroup$ I can see that choosing 2 elements from n would give $\frac{n(n-1)}{2}$ yet I can't see how it enables us to progress from 3 to 4, or 4 to 5 for that matter. $\endgroup$ – Charlie Egan Feb 22 '14 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.