Log in

View Full Version : Proof by induction


svenghart
Dec 11, 2006, 03:09 PM
I need help in figuring out how to prove 1+2n is less than or equal to 3^n by using induction.

galactus
Dec 11, 2006, 05:59 PM
Prove by induction: 1+2n<=3^n

#1. P_1 is true, since 1+2(1)<=3^1

#2. Assume P_k is true, 1+2k<=3^k.

Now, 1+2(k+1)<=3(1+2k) for k>=1--->2k+3<6k+3

We can see that 3(1+2k)<=3*3^k

3(1+2k)<=3^(k+1)

And conclude that 1+2(k+1) <= 3^(k+1)