Demostrando la relación de recurrencia con inducción: $T(n) = T(n-1) + n$

Question

Tengo que probar que el límite de la relación siguiente es $\theta(n^2)$ de admision

$$T(n) = T(n-1) + n$$

1. debería seprate mi inducción en dos secciones - pretender que $T(n) = O(n^2)$ y $T(n) = \Omega(n^2)$ y probar cada caso, o ¿debo ampliar la relación y después formular mi reclamo?
2. mis dos ecuaciones deben lo mismo, pero con distinto signo--> $\leq$ y $\geq$

¡Gracias!

Answer 1

Otro camino para difundir una luz diferente. De la identidad, $$ T {n} = T {n-1} + n, \qquad n = 1, 2, 3, \ldots, $$ se puede obtener $$ T {n} - T {n-1} = n, $$ then summing from $n = 1 $ to $n = N$ términos telescopio, $$ T_N - T0 = \sum {n = 1} ^ {N} n, $ lo $$ T_N - T_0=\frac{N(N+1)} 2 $$ giving, as $N \to \infty$ ,

$$ \frac{N^2}2\leq T_N \leq N ^ 2 $$

como quería.