Challenges with Induction Proofs: Strategies and Solutions

[ekko]

hello, i am having some trouble with a few induction problems.

1) Prove by induction that for all natural numbers n, n^2 + 3 < 2^n + 5.

2) Prove by induction that for all natural numbers n, (1-1/2)(1-1/4)...(1-1/(2^n)) > or equal to 1/4 + 1/(2^(n+1)).

i got started on these but ran into dead-ends for both of them.

 

[tiny-tim]

Welcome to PF!

Hi ekko! Welcome to PF!

Show us the first few lines of your attempt at 1)

 

[sutupidmath]

if n>3 i could easily prove the first one, but for every n from naturals, i am going to have to have a closer look at it!

 

[ekko]

ok well for 1) i first state that 1^2 +3 = 4 and 2^1 + 5 = 7, so 4 < 7. Therefore the statement is true for n = 1. then i assume that for some natural number n, n^2 +3 < 2^n + 5, and i have to prove from this that (n+1)^2 +3 < 2^(n+1) + 5. so first i multiplied both sides by 2 (which doesn't change the < because 2 is positive), which gives me 2*(n^2) + 6 < 2^(n+1) +10. Then I subtracted 5 from both sides and got 2*(n^2) + 1 < 2^(n+1) + 5. Now the right side of the statement looks like what i want to prove, but i can't figure out how the make the left side equal (n+1)^2 +3 .

 

[CompuChip]

It doesn't have to be equal, it can also be more
For example:

(n + 1)^2 + 3 = n^2 + 2n + 2 + 3 = (n^2 + 3) + 2n + 2
Now use the induction hypothesis to make an estimate or a series of estimates:
(n + 1)^2 + 3 < ... <= ... <= ... < 2^(n+1) + 5

 

[ekko]

i still don't get it. i don't know which estimates to use to make the proof work. i have to get from (n+1)^2 + 3 < ... <= ... <= ... 2*(n^2) +1 < 2^(n+1) +5. one thing i can do is expand this to n^2 + 2n +1 + 3 < ... n^2 + n^2 + 2n +4 < 2*(n^2) +2n +4, but how is that last term less than or equal to 2*(n^2) +1?

 

[tiny-tim]

i still don't get it. i don't know which estimates to use to make the proof work. i have to get from (n+1)^2 + 3 < ... <= ... <= ... 2*(n^2) +1 < 2^(n+1) +5. one thing i can do is expand this to n^2 + 2n +1 + 3 < ... n^2 + n^2 + 2n +4 < 2*(n^2) +2n +4, but how is that last term less than or equal to 2*(n^2) +1?

Yes, that's what I tried first : and it doesn't seem to work!

Then I tried a few examples, comparing n^2 with 2^n, and for n = 1 … 5, the pairs come out as:
1,2; 4,4; 9,8; 16,16; 25,32;
so obviously the n^2 is increasing by (1 + 1/n)^2, but the 2^n is increasing by 2;
once 1/n < √2 - 1, the 2^n always increases faster!
1/n < √2 - 1 = .414 means n ≥ 3.

That's the principle, ekko - now see if you can write it out properly!

(And then show us the first few lines of your attempt at 2).)

 

[sutupidmath]

yeah, that is exactly whit i tried out, and like i said on my post #3 it is valid for n>3, it doesn't even work for n=3. And once we have set this extra condition the proof is quite straightforward.

 

[tiny-tim]

yeah, that is exactly whit i tried out, and like i said on my post #3 it is valid for n>3, it doesn't even work for n=3.

Yes, but there's nothing to stop ekko proving it for n = 1 2 and 3 just by working it out for those values, and then starting the induction from there!