Show (not by giving a $(c,k)$ pair but in some other way) that the sum of the squares of the first $n$ odd positive integers is of order $n3$. I.e. is that sum $\Theta(n3)$?

Hint: Try to find a closed-form formula for that summation. That will take you to the exact order of growth.

  • $\begingroup$ What did you try up to now ? $\endgroup$ – Claude Leibovici Nov 26 '13 at 8:45

You begin with,

$$1^2 + 3^2 + 5^2 + \ldots = \sum\limits_{k=1}^n (2k-1)^2$$

You can expand this expression in the following manner.

$$\sum\limits_{k=1}^n (2k-1)^2 = \sum\limits_{k=1}^n 4k^2 - \sum\limits_{k=1}^n 4k + \sum\limits_{k=1}^n 1$$

$$ = 4\sum\limits_{k=1}^n k^2 - 4\sum\limits_{k=1}^n k + \sum\limits_{k=1}^n 1 $$

Now you just need to evaluate the three terms individually.

$ \sum\limits_{k=1}^n 1 = n $ is trivial. This of order $n$, so that's not helpful for your purposes.

$2\sum\limits_{k=1}^n k = (1+2+\ldots+(n-1)+n)+(n + (n-1) + \ldots + 2 + 1) = n(n+1)$. So,

$\sum\limits_{k=1}^n k $ is of order $n^2$ which doesn't work either.

Now you just have to find if $\sum\limits_{k=1}^n k^2$ is of order $n^3$.

  • 1
    $\begingroup$ This is homework. I think that explaining how to arrive to the result would be more interesting to the OP. $\endgroup$ – Claude Leibovici Nov 26 '13 at 8:53
  • 1
    $\begingroup$ @NikhilMajahan. This in incredibly much more useful ! Thanks for taking the time of doing it. $\endgroup$ – Claude Leibovici Nov 26 '13 at 9:08

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.