Cómo demostrar a $f(n+1) = f(n)+n+1$$O(n^2)$?

Question

Ingeniero de Software aquí; he escrito un pequeño programa que demuestra que para la siguiente función:

$$f(n+1) = f(n)+n+1$$

comenzando con

$$f(0)=0$$

la siguientes es verdadera:

$$\lim_{n\to \infty}\left(f(n)\right) = \frac{n^2}{2}$$

y por lo tanto el Big-O notación que mejor describe la función es $O(n^2)$. No tengo idea de cómo demostrarlo formalmente, aunque. Alguien puede ayudar?

Answer 1

Podemos escribir la relación como $f(n+1) - f(n ) = n+1.$ $$ f(n) = (f(n) - f(n-1) ) + (f(n-1) - f(n-2) ) + \cdots + (f(1) - f(0) ) + f(0) $$

$$ = n+ (n-1) + (n-2) + \cdots +1 = \frac{n(n+1)}{2}.$$