Is this summation correct?:
$\sum_{i=1}^{n} (i \cdot i)$
How would I go about proving that the statement is $O(n^3)$?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Where is an equation and where is the recurrence? $\endgroup$– amsmathCommented Oct 10, 2017 at 14:42
-
$\begingroup$ I'm not sure, I just thought that this was similar to recurrence equations that I've seen. What would be the proper question to ask? $\endgroup$– Godron629Commented Oct 10, 2017 at 14:43
-
$\begingroup$ We have $(n+1)^3-n^3 = 3n^2+3n+1$, hence $$ \sum_{i=1}^{n} i^2 \leq \frac{1}{3}\sum_{i=1}^{n}\left((i+1)^3-i^3\right)\le\frac{(n+1)^3}{3}=O(n^3). $$ $\endgroup$– Jack D'AurizioCommented Oct 10, 2017 at 16:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
Because it's $$\frac{n(n+1)(2n+1)}{6},$$ which we can get by the telescopic sum.
answered Oct 10, 2017 at 14:38
-
$\begingroup$ I am interested in your telecopic sum... $\endgroup$– amsmathCommented Oct 10, 2017 at 14:48
-
$\begingroup$ @amsmath Use $(n+1)^3-n^3=3n^2+3n+1$ and $1+2+...+n=\frac{n(n+1)}{2}.$ $\endgroup$ Commented Oct 10, 2017 at 14:52
-
-
$\begingroup$ I realize now ( after purchasing the class textbook and spending 5 minutes in the appendix) that this question is the Sum of Squares. Thanks for your answer. $\endgroup$ Commented Oct 10, 2017 at 23:54
-
$\begingroup$ @Godron629 You are welcome! $\endgroup$ Commented Oct 11, 2017 at 3:18
$\begingroup$
$\endgroup$
11
Given that you only need $O(n^3)$, a possible answer would be that $$ \sum_{i=1}^n i^2 \leq \sum_{i=1}^n n^2 \leq n\times n^2 = n^3. $$ and $$ \sum_{i=1}^n i^2\ge\sum_{i=2}^ni(i-1)=\frac13\sum_{i=2}^n[(i+1)i(i-1)-i(i-1)(i-2)]=\frac{n(n^2-1)}3\ge\frac13n^3. $$
answered Oct 10, 2017 at 14:39
-
2$\begingroup$ I think it's not enough. We can get also that $\sum\limits_{i=1}^ni^2<n^{1000}$ $\endgroup$ Commented Oct 10, 2017 at 14:40
-
2$\begingroup$ I think it's a total wrong answer. @Alberto Debernardi The down vote is not mine. $\endgroup$ Commented Oct 10, 2017 at 14:44
-
1$\begingroup$ @MichaelRozenberg No, it is completely correct. Look up the $O$-notation. $\endgroup$– amsmathCommented Oct 10, 2017 at 14:45
-
2$\begingroup$ @MichaelRozenberg I did. So what? He proved that there is a positive constant such that the expression is $\le Cn^3$. $\endgroup$– amsmathCommented Oct 10, 2017 at 14:47
-
2$\begingroup$ The $O$-notation stands for an upper estimate, not lower. $\endgroup$ Commented Oct 10, 2017 at 14:51