Q:

prove recursive sequence via induction

I'm trying to prove a recursive sequence via induction. However, this question is quite different from what is being taught from the lecture. The basics of where I can assume a base case $n = 1$, and a case of $n - 1$ or $n + 1$ thereafter. Next, the question may provide like some basic formula like adding different cases to get a fixed formula to the sequence, 
However, in this question

$_ = 0$ where $n = 0$, //may use this as a base case
$_ = _{−1} + $ where $ \ge 1$

What I attempt is to allow the first function $_ = 0$ where $n= 2$ , while the second function $_ = 1$ where $n = 1$, and the third function $_ = 3$ where $n = 2$.
I'm suppose to prove by induction that for all $n \ge 0$, the solution is $_ = (n^2 + n)/2$.
How do I even know how to combine them together without knowing any prior formula to this? 

A:

OK, let's review what you know:

You know $f_0=0$.
You know that $f_n = f_{n-1} + n$ for $n\geq 1$.

You want to prove the claim
$$\forall n: f_n=\frac{n^2+n}{2}.$$

A proof by induction of a claim $P(n)$ (in our case, $P(n)$ is $f_n=\frac{n^2+n}{2}$) always has two steps:
Step 1:
Prove that the claim is true for $n=0$. In other words, you want to prove $P(0)$, in our case you want to prove $f_0=\frac{0^2+0}{2}$, which is fairly easy to prove.
Step 2:
Assume that $P(n)$ is true. Now you need to prove $P(n+1)$ is also true. In particular, you want to prove that $$f_{n+1} = \frac{(n+1)^2 + n+1}{2}$$ while you assume that $f_n=\frac{n^2+n}{2}$ is true.
You can now use the fact that $f_n = f_{n-1} + n$, which means the claim $$f_{n+1} = \frac{(n+1)^2 + n+1}{2}$$ (which you want to prove) is equivalent to $$f_{n} + n+1 = \frac{(n+1)^2 + n+1}{2}.$$
Now, just use the fact that you already know $f_n=\frac{n^2+n}{2}$ is true, plug in the value, and you are done.

