Fórmula de forma cerrada

Question

Mostrar (no dando un $(c,k)$ pero de otra manera) que la suma de los cuadrados del primer $n$ impar enteros positivos es de orden $n3$ . Es decir, es esa suma $\Theta(n3)$ ?

Pista: Intenta encontrar una fórmula de forma cerrada para ese sumatorio. Eso te llevará al orden exacto de crecimiento.

Answer 1

Comienza con,

$$1^2 + 3^2 + 5^2 + \ldots = \sum\limits_{k=1}^n (2k-1)^2$$

Puedes ampliar esta expresión de la siguiente manera.

$$\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 $$

Ahora sólo hay que evaluar los tres términos individualmente.

$ \sum\limits_{k=1}^n 1 = n $ es trivial. Esto de orden $n$ así que eso no es útil para sus propósitos.

$2\sum\limits_{k=1}^n k = (1+2+\ldots+(n-1)+n)+(n + (n-1) + \ldots + 2 + 1) = n(n+1)$ . Así que,

$\sum\limits_{k=1}^n k $ es de orden $n^2$ que tampoco funciona.

Ahora sólo tienes que encontrar si $\sum\limits_{k=1}^n k^2$ es de orden $n^3$ .