Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trouble with induction proofs

  1. Mar 6, 2008 #1
    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.
     
  2. jcsd
  3. Mar 6, 2008 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Welcome to PF!

    Hi ekko! Welcome to PF! :smile:

    Show us the first few lines of your attempt at 1) :smile:
     
  4. Mar 6, 2008 #3
    if n>3 i could easily prove the first one, but for every n from naturals, i am gonna have to have a closer look at it!
     
  5. Mar 6, 2008 #4
    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 .
     
  6. Mar 6, 2008 #5

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    It doesn't have to be equal, it can also be more :smile:
    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
     
  7. Mar 6, 2008 #6
    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????
     
  8. Mar 7, 2008 #7

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

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

    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! :smile:

    (And then show us the first few lines of your attempt at 2).)
     
  9. Mar 7, 2008 #8
    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.
     
  10. Mar 7, 2008 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    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! :smile:
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Trouble with induction proofs
  1. Proof by Induction (Replies: 7)

  2. Proof by Induction (Replies: 2)

Loading...