Prove by induction that $n^2 + n + 1 \forall n\geq 1$ given the following recurrence relation

Question

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.

Answer 1

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.

Answer 2

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$.

Answer 3

In a nutshell,

$$3=1^2+1+1$$ and

$$n^2+n+1=(n-1)^2+(n-1)+1+2n$$ are both true.