Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Please could someone advise on my solution to the following problem. Am I wording this right or could you offer a better way?

Question is to show that $S_n =O(n^3)$ where $S_n = \sum_{k=1}^n(k^2)$

Solution: $$\begin{align*}S_n &= n(a_1 + a_n)/ 2 \quad\leftarrow \text{sum of series} \\ &= n(1 + n^2)/2 \\ &= n/2 + n^3/2\end{align*}$$

Since $n^3$ is the dominant term the Big-O estimate is $O(n^3)$

Should this be worded differently?

cheers

share|improve this question
    
The sum isn't $n(1 + n^2)/2$. This is applicable only when the difference between successive terms is constant. Here it increases by $2$ for each term. Rather, the formula for the sum is $n(n + 1)(2n+1)/6$ –  Arthur Oct 9 '12 at 10:31
    
Cheers Arthur..What am I doing wrong with the formatting? For instance it does not seem to be displaying the exponent correctly when I use, for example, S_n =O(n^3)..any thoughts? –  bosra Oct 9 '12 at 10:31
    
You need to enclose math within dollar signs, and within double dollar signs when you want bigger expressions in separate lines. This also makes writing actual dollar signs a bit tricky, you need to type a backslash before the \$-sign. –  Arthur Oct 9 '12 at 10:32
    
ok many thanks for your replies –  bosra Oct 9 '12 at 10:33
    
If you click the "edit"-button on the bottom right of the question box, you can see how I, or rather Brian M. Scott, formatted your question. If you don't want to change anything, you can just press "Cancel" –  Arthur Oct 9 '12 at 10:35

1 Answer 1

As Arthur pointed out in the comments, your exact expression for $\sum_{k=1}^nk^2$ is wrong, but you don’t actually need to know one in order to show that $S_n$ is $O(n^3)$: just note that $$S_n=\sum_{k=1}^nk^2\le\sum_{k=1}^nn^2=n^3\;.$$

share|improve this answer
    
Thanks for that Brian. So I was mistakenly using the arithmetic sum of series formula. Should I have been using the geometric sum of the series formula given that each term is increasing by a common ratio? Thanks –  bosra Oct 9 '12 at 10:58
    
@bosra: They aren’t increasing by a common ratio: $\frac{(k+1)^2}{k^2}=\left(\frac{k+1}k\right)^2=\left(1+\frac1k\right)^2$, whose value depends on $k$. The sequence of squares is neither arithmetic nor geometric. Either you need the actual formula for the sum of the first $n$ squares, which Arthur gave in his first comment, or you might as well just use the very simple argument that I gave in my answer. –  Brian M. Scott Oct 9 '12 at 11:03
    
Ok thank you both –  bosra Oct 9 '12 at 11:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.