Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
    
Ah I see, thank you! Dropping the = makes sense, but does doing so change the proof? –  xlm Mar 1 '12 at 8: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 1 '12 at 9:34
    
Apologies for not adding it earlier, base is n=1 since the proof is for n>=1 –  xlm Mar 1 '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 3 '12 at 9:08
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.