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:
$$\sum_{i=5}^n\sum_{j=2}^{n+i}3ji,\;for\;n\ge5$$
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:
$$\sum_{i=5}^n3i\sum_{j=2}^{n+i}j$$
Then I solved the inner sum:
$$\sum_{i=5}^n3i\;\left(\,\sum_{j=1}^{n+1}j-\sum_{j=1}^1j\,\right)$$
$$\sum_{i=5}^n3i\left(\frac{(n+i)(n+i+1)}{2}-1\right)$$
$$\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:
$$\frac{3}{2}\left(17n^4+34n^3-113n^2-850n-1320\right)$$
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.
Best Answer
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.