Simplifying Multiple Summations for worst case analysis

Question

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

Answer 1

$\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$.

Answer 2

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