- #1

- 66

- 0

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?

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: