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: 3n≥1+2n
Skipping past the base case and assuming it's true, the books inductive step is as follows:
Show: 3n+1=1+2(1+n)
LHS =3⋅3n
LHS ≥3(1+2n) [by assumption]
LHS ≥1+2+2n+4n [algebra]
LHS ≥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!
Answer
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.
No comments:
Post a Comment