1

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.

nullgeppetto
  • 3,006
user111557
  • 19

1 Answers1

0

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

XYZT
  • 1,043
  • 6
  • 22