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

  • $\begingroup$ 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. $\endgroup$ – 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.

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

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.