

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

I have this question on my assignment for a computer science course (analysis of algorithms), so any help would be appreciated, but I am not looking for the answer itself.

I am trying to find the closed form solution for the following:


Since i = 5, n will always be $\ge5$, so I'm not sure why that's specified, unless I'm wrong about that.

The first thing I did was to factor out 3i:


Then I solved the inner sum:



$$\frac{3}{2}\sum_{i=5}^ni\,(i^2 + 2in + i + n^2 + n - 2)$$

I then tried to separate each term into different summations, combining terms treating n as a coefficient. I multiply each term by $12$ to get a common denominator, and then collect all the terms. The result I get is:


Which is almost correct.

Does anyone know why the coefficient would change from $\frac{3}{2}$ to $\frac{1}{8}$ while solving it? I don't understand that part.

share|cite|improve this question
up vote 4 down vote accepted

You are going to have terms such as $\sum_i i^2$ and $\sum_i i^3$. It turns out that there are simple expressions for these:

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

$$\sum_{i=1}^n i^3 = \left [ \frac{n (n+1)}{2} \right ]^2 $$

Collect terms in $i$, $i^2$, and $i^3$ in your sum and use these expressions. Shouldn't be too bad.

share|cite|improve this answer
Thanks! I forgot I could treat n as a coefficient. I need to remind myself that these nested summations are similar to partial derivatives in that respect. – MichaelThiessen Jan 25 '13 at 23:24

Your Answer


