# How to prove $f(n+1) = f(n)+n+1$ is $O(n^2)$?

Software engineer here; I've written a little program which demonstrates that for the following function:

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

starting with

$$f(0)=0$$

the following is true:

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

and therefore the Big-O notation which best describes the function is $O(n^2)$. I have no idea how to prove it formally, though. Can anyone help?

-
Also, if anyone would like to help tag this properly, that would be splendid. :-) – bythescruff Dec 10 '12 at 12:30
$\lim_{n\to \infty} f(n) = \infty$, not $\frac{n^2}{2}$. – user1551 Dec 10 '12 at 12:47
@user1551 True; I didn't quite know how to say, "As n gets bigger, values of f(n) get closer to values of (n^2)/2" formally. :-) – bythescruff Dec 10 '12 at 13:14
@bythescruff In the future you could use the asymptotic notation: $f\sim g$ if $f/g \to 1.$ So here you could have wrote $f\sim n^2/2.$ – Ragib Zaman Dec 10 '12 at 13:22
@bythescruff "As n gets bigger, values of $f(n)$ get closer to values of $n^2/2$". This is formal enough, isn't it? ;-D By the way, this formal statement is false too. $f(n)$ does not get closer to $n^2/2$ when $n$ is getting large. In fact, $f(n)$ departs from $n^2/2$ more and more when $n\rightarrow\infty$. The ratio $f(n)/(n^2/2)$ does approach 1, though. As pointed out by Ragib Zaman, this is usually written as $f\sim n^2/2$. – user1551 Dec 10 '12 at 13:28

We can write the relation as $f(n+1) - f(n ) = n+1.$ Thus, $$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}.$$
@bythescruff In the first line, we express $f(n)$ as a sum of many terms of the form $f(i) - f(i-1).$ By the relation, we know that these $f(i)-f(i-1)=i$, and putting $i$ in place of the $f(i)-f(i-1)$ gives the second line. – Ragib Zaman Dec 11 '12 at 12:45