# Simplifying Multiple Summations for worst case analysis

I'm figuring out a worst case analysis on a function. After converting it to a set of summations, and changing the sigma notations into summation formuale I ended up with:

N(N+1)(2N+1) / 6    +    N    -     N(N+1) / 2


Using LCD i was able to combine the first two components as:

 N(N+1)(2N+1) + 6N / 6


Leaving me with:

 N(N+1)(2N+1) + 6N / 6     -     N(N+1) / 2


Using LCD again, I'm guessing I would use an LCD of 6 then combine the two fractions as i did the first. But i am having trouble converting the top line of the second fraction. Do I multiply the whole expression by 3, or just numerics?

Many Thanks

$\dfrac{N(N+1)(2N+1)}{6} + N - \dfrac{ N(N+1)}{ 2}$

$=\dfrac{N(N+1)(2N+1)}{6} + \dfrac{6 N}{6} - \dfrac{ 3N(N+1)}{ 6}$

$=\dfrac{N(N+1)(2N+1) + 6 N - 3N(N+1)}{ 6}$

and you can simplify the numerator.

Incidentally this is $\displaystyle\sum_{i=1}^N i^2+1-i$ so it is quite easy to check your result for various small values of $N$.

• This is what i would have written, but incidentally my friend got toN(N+1)(2N+1-3)+6N/6 I just couldn't understand the missing transition in between. – user1475128 Oct 14 '13 at 13:36

A good hint would be to write the second fraction as $$\frac{3N(N+1)}{6}$$ and then combine it with the first one.

• Nice hint, my friend! +1 – amWhy Oct 14 '13 at 15:16
• @amWhy: Thanks Amy for the support. ;-) – Mikasa Oct 14 '13 at 17:25