# Closed-form formula

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.

• What did you try up to now ? – 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$.

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