demuestre que $\sum_{i=1}^n i^2$ es $O(n^3)$

Question

Para empezar, ¿voy por buen camino?

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

¿Adónde iría a partir de ahora?

Answer 1

Usted es así que cerca.

Voy a escribir lo que hiciste utilizando la notación sumatoria y lo terminaré.

$\begin{array}\\ \sum_{i=1}^n i^2 &\le \sum_{i=1}^n n^2 \qquad\text{since } i \le n\\ &= n^2\sum_{i=1}^n 1 \qquad\text{taking }n^2\text{ out of the sum}\\ &= n^3 \qquad\text{since }\sum_{i=1}^n 1 = n\\ \end{array} $

He aquí un caso más general.

$\begin{array}\\ \sum_{i=1}^n i^m &\le \sum_{i=1}^n n^m \qquad\text{since } i \le n\\ &= n^m\sum_{i=1}^n 1 \qquad\text{taking }n^m\text{ out of the sum}\\ &= n^{m+1} \qquad\text{since }\sum_{i=1}^n 1 = n\\ \end{array} $

Esto demuestra que $\sum_{i=1}^n i^m =O(n^{m+1}) $ .

Answer 2

El enfoque de la fuerza bruta:

Tenemos

$\sum_1^n i^2 = \dfrac{n(n + 1)(2n + 1)}{6}, \tag{1}$

que de hecho es muy muy conocida: basta con buscar en Google algo como "suma de los n primeros cuadrados" para obtener un millón de resultados.

Es bastante fácil demostrar (1) por inducción; para $n = 1$ vemos que (1) se reduce a

$1^2 = 1 = \dfrac{1(2)(3)}{6}; \tag{2}$

sólo por diversión comprobamos los casos $n = 2, 3$ :

$1^2 + 2^2 = 1 + 4 = 5 = \dfrac{2(3)(5)}{6}; \tag{3}$

$1^2 + 2^2 + 3^2 = 1 + 4 + 9 = 14 = \dfrac{3(4)(7)}{6}; \tag{4}$

A partir de aquí, un simple paso inductivo se impone: si

$\sum_1^k i^2 = \dfrac{k(k + 1)(2k + 1)}{6}, \tag{5}$

entonces

$\sum_1^{k + 1} i^2 = \sum_1^k i^2 + (k + 1)^2 = \dfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2; \tag{6}$

molemos por la derecha:

$\dfrac{k(k + 1)(2k + 1)}{6} + (k + 1)^2 = \dfrac{k(k + 1)(2k + 1)}{6} + \dfrac{6(k + 1)^2}{6}$ $= \dfrac{k(k + 1)(2k + 1) + 6(k + 1)^2}{6}; \tag{7}$

ahora,

$k(k + 1)(2k + 1) = (k^2 + k)(2k + 1) = 2k^3 + 3k^2 + k, \tag{8}$

y así

$k(k + 1)(2k + 1) + 6(k + 1)^2 = 2k^3 + 3k^2 + k + 6k^2 + 12k + 6$ $= 2k^3 + 9k^2 + 13k + 6, \tag{9}$

y también

$(k + 1)(k + 2)(2(k +1) + 1) = (k^2 + 3k + 2)(2k + 3)$ $= 2k^3 + 3k^2 + 6k^2 + 9k + 4k + 6 = 2k^3 + 9k^2 + 13k + 6, \tag{10}$

por lo que vemos que

$k(k + 1)(2k + 1) + 6(k + 1)^2 = (k + 1)(k + 2)(2(k + 1) + 1), \tag{11}$

y combinando (6), (7) y (11):

$\sum_1^{k + 1} = \dfrac{(k + 1)(k + 2)(2(k + 1) + 1)}{6}, \tag{12}$

lo que completa el paso inductivo y nos permite concluir que

$\sum_1^n i^2 = \dfrac{n(n + 1)(2n + 1)}{6} \tag{12}$

para todos los enteros positivos $n$ . Utilizando (8), escribimos (12) como

$\sum_1^n i^2 = \dfrac{2n^3 + 3n^2 + n}{6} = n^3\dfrac{2 + 3n^{-1} + n^{-2}}{6}; \tag{13}$

desde

$\dfrac{2 + 3n^{-1} + n^{-2}}{6} \to \dfrac{1}{3} \tag{14}$

como $n \to \infty$ vemos que

$\sum_1^n i^2 = O(n^3). \tag{15}$

Answer 3

Equivale a

$$ \lim_{n \to \infty}{\sum_{k = 1}^{n}k^{2} \over n^{3}} = \lim_{n \to \infty} {\left(\,n + 1\,\right)^{2} \over \left(\,n + 1\,\right)^{3} - n^{3}} = \lim_{n \to \infty} {\left(\,1 + 1/n\,\right)^{2} \over 3 + 3/n + 1/n^{2}}\ =\ \bbox[10px,#ffe,border:1px dotted navy]{\displaystyle{1 \over 3}} $$