0
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Jamgreen
    Commented Dec 5, 2014 at 12:52
  • $\begingroup$ 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? $\endgroup$
    – Jamgreen
    Commented Dec 5, 2014 at 13:01
  • $\begingroup$ Then $$n + 2^n + 2(n-1)^2 = 2^n + 2n^2 -n + 2 > 2^n + n^2$$ Because $n^2 - n + 2 > 0$. $\endgroup$
    – peterwhy
    Commented Dec 5, 2014 at 13:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .