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

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?

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.
• But $a_{n-1}$ is not equal to $2^{n-1} + (n-1)^2$ but greater than or equal to so I would not think that I could simply substitute these? Commented Dec 5, 2014 at 12:52
• But if I use your strategy I get $n+2 (2^{n-1}+(n-1)^2) \geq 2^n + n^2 \Leftrightarrow -3n+n^2+2 \geq 0$. I can see that for any $n$ the inequality is true but it seems to me that I now have a new problem to proof? Commented Dec 5, 2014 at 13:01
• Then $$n + 2^n + 2(n-1)^2 = 2^n + 2n^2 -n + 2 > 2^n + n^2$$ Because $n^2 - n + 2 > 0$. Commented Dec 5, 2014 at 13:27