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

Homework Help: Induction Proof

  1. Jan 13, 2009 #1
    I'm just wondering if this is a legitimate proof by induction.

    Prove, for all natural numbers [tex]n[/tex], that [tex]2^n>n[/tex]

    Proof. For [tex]n=0[/tex], [tex]2^0=1>0[/tex] and for [tex]n=1[/tex], [tex]2^1=2>1[/tex]. Similarly, if [tex]n=2[/tex], then [tex]2^2=4>2[/tex]. Now assume [tex]n>2[/tex] and we have proven the result for [tex]n-1[/tex]. We must show it is true for [tex]n[/tex].

    We have:

    [tex]
    2^{n-1}>n-1
    [/tex]

    [tex]
    2^n>2(n-1)=(n-1)+(n-1)>(n-1)+1=n
    [/tex]

    The last inequality follows from the fact that [tex]n>2[/tex].

    I'm worried about the fact that I have more than one base case. Is this still alright?
     
    Last edited: Jan 13, 2009
  2. jcsd
  3. Jan 13, 2009 #2
    Looks right. Doesn't matter how many base cases you have as long as you cover all natural numbers in the end.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook