0

I've been able to follow the idea and steps of induction so far but I've hit a road block in understanding one of the examples in a text book. This is what the book says p.97:

Prove: $3^n \geq1 + 2n$

Skipping past the base case and assuming it's true, the books inductive step is as follows:

Show: $3^{n+1} = 1 + 2(1+n)$

LHS $= 3\cdot 3^n $
LHS $\geq 3(1+2n)$ [by assumption]
LHS $\geq 1+2+2n+4n$ [algebra]
LHS $\geq 1+2(1+n)$ [since $n>0$]

How can the $4n$ be omitted by $n>0$? This really boggles me, appreciate any insights and help.

Thanks!

Gerry Myerson
  • 179,216
xlm
  • 333

2 Answers2

1

If n>0 then 4n>0 and omitting it from the RHS reduces the value. So >= still applies - or applies more strongly, and the = could be dropped.

Mark Bennet
  • 100,194
  • Ah I see, thank you! Dropping the = makes sense, but does doing so change the proof? – xlm Mar 01 '12 at 08:14
  • @xlm, it forces you to add the condition $n > 0$ and prove a new base case. Edit: hang on... is the base case not $n=0$? If not, why not? Equality holds then... I would have thought it should be $n \ge 0$, in which case you can't drop the $=$. – Peter Taylor Mar 01 '12 at 09:34
  • Apologies for not adding it earlier, base is n=1 since the proof is for n>=1 – xlm Mar 01 '12 at 13:18
  • Apologies for ambiguity there - I was not referring to the base case in dropping the equality, but to the inductive step. It is exploring such things which leads to extensions and generalisations. – Mark Bennet Mar 03 '12 at 09:08
0

Since $n>0$, we have $4n>0$ so $1+2+2n+4n>1+2+2n=1+2(1+n)$, thus $\text{LHS}\geq 1+2(1+n)$.

Alex Becker
  • 60,569