Proof by induction that if $a_0 = 1$ and $a_n = n + 2 a_{n-1}$, then $a_n \ge 2^n + n^2$.

Question

I have that $a_0 = 1$ and $a_n = n + 2 a_{n-1}$ for $n \geq 1$.

Now I need to proof by induction that $a_n \geq 2^n + n^2$.

I already have my base case.

My hypothesis would be $a_{n-1} \geq 2^{n-1} + (n-1)^2$.

Now I need to show the inductive step $$ a_n = n+2 a_{n-1} \geq 2^n + n^2 $$ but how can I now use my hypothesis to show that the inductive step works? Should I isolate $a_{n-1}$ as $$ a_{n-1} \geq \frac{1}{2} (2^n+n^2-n) $$ and compare it with the hypothesis?

I have read alot about proof by induction but I still need to become better at it. Can anyone suggest any tips and tricks?

Answer 1

You should probably just substitute what you know, i.e. $$ a_n=n+2a_{n−1}\geq n+2*\left(2^{n−1}+(n−1)^2\right) $$ and manipulate that. It doesn't look that hard to get what you need.