Prove by induction that $n^2 + n + 1 \forall n\geq 1$ given the following recurrence relation My question is as follows:
Consider the following recurrence relation:
$a_{n} = a_{n-1}+2n$, with $a_{1}=3$
Prove by induction that
$a_{n}=n^{2}+n+1 \forall  n\geq 1$
I have no idea how to even approach this question. I am quite familiar with the process of induction but am just unsure how to draw that in for this question? I am not very familiar with recurrence relations.
 A: In a nutshell,
$$3=1^2+1+1$$ and
$$n^2+n+1=(n-1)^2+(n-1)+1+2n$$ are both true.
A: Suppose true for $n$, $a_{n+1}=n^2+n+1+2(n+1)=(n^2+2n+1)+(n+1)+1=(n+1)^2+(n+1)+1$.
A: Induction is usually achieved in three steps.
1) Initialization. You just need to check that your property is valid for the lowest integer required (here $n = 1$). So what you need to check is that indeed, $a_1 = 1^2 + 1 + 1$.
2) Heredity. This step is usually the most difficult, and you have to be careful when writing it. At this point, you assume that your property is valid for some $n \geq 1$ (and certainly not for all $n$, in which case there is nothing left to show).
Therefore, you assume that, for some $n \geq 1$, $a_n = n^2 + n + 1$. Now use the recurrence relation to deduce that $a_{n+1} = (n+1)^2 + (n+1) + 1$. 
3) Conclusion. In step 2, you have shown that if your property is valid at rank $n$, it is also valid at rank $n+1$. In step 1, you have shown that the property is valid at rank 1. Thus, the property is valid at rank 1+1 = 2, then at rank 2+1 = 3,... and finally for any $n \geq 1$. This step is usually skipped once one is familiar with the whole induction process. 
