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

A Proof by induction

  1. Oct 14, 2004 #1
    Prove that for all n in the natural numbers 3^n greater than or equal to 1+2^n.

    Here's my start:
    3^1 greater than or equal to 1+2^1, so the statement is true for n=1.
    Assume that for some n, 3^n greater than or equal to 1+2^n
    Then 3^n+3^n+3^n greater than or equal to 1+2^n +3^n+3^n.
    It follows that 3^(n+1) greater than or equal to 1+2^n+2*3^n.

    Where do I go from here? I still need to show that 1+2^n+2*3^n is greater than or equal to 1+2^(n+1)

    Last edited: Oct 14, 2004
  2. jcsd
  3. Oct 14, 2004 #2


    User Avatar
    Science Advisor
    Homework Helper

  4. Oct 14, 2004 #3


    User Avatar
    Science Advisor

    To show 3n+1>1+2n+1
    subtract the n expressions from both sides, and you will have to show
    That looks obviously true,since 3>2.
  5. Oct 14, 2004 #4
    good work mathman!!!
  6. Oct 16, 2004 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    So you'd like to prove that

    [tex]3^n\geq 1+2^n[/tex]

    using induction. The statement is obviously true for n=1, so all you have to do is to prove that if it's true for n=k, it's also true for n=k+1 (whatever k is).

    So you should start like this:

    [tex]3^{k+1}=3\cdot 3^k\geq 3(1+2^k)\geq\dots[/tex]

    Now all you have to do is to show that this is

    [tex]\geq 1+2^{k+1}[/tex]

    This is very easy. (Hint: 3>2>1).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook