¿Cómo puedo demostrar que $\sum \limits_{i=1}^n i^2$ es $O (n^3)$

Question

Estoy preparando un examen y uno de los problemas de la guía de estudio es:

Demostrar que $\sum \limits_{i=1}^n i^2$ es $O (n^3)$

Si declaramos n como un número arbitrario 5, entonces nuestra suma sería $1^2$ + $2^2$ + $3^2$ + $4^2$ + $5^2$

Todo lo que he investigado me sugiere que esto debería ser $O (n^2)$ . ¿Cómo podemos llegar a $O (n^3)$ ?

Answer 1

Sugerencia: Tenga en cuenta que

$$\sum_{i=1}^n i^2 = 1^2 + 2^2 + \cdots + n^2 \le n^2 + n^2 + \cdots + n^2.$$

Answer 2

No es difícil demostrar que \begin{align} \sum_{i=1}^{n} i^{2} = \frac{n(n+1)(2n+1)}{6} = \frac{n^{3}}{3} + \frac{n^{2}}{2} + \frac{n}{6} \end{align} Dado que la mayor potencia en $n$ es 3 entonces se puede afirmar que \begin{align} \sum_{i=1}^{n} i^{2} \sim \mathcal{O}(n^{3}) \end{align}