Induction Proof

  • Thread starter altcmdesc
  • Start date
  • #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?
 
Last edited:

Answers and Replies

  • #2
179
0
Looks right. Doesn't matter how many base cases you have as long as you cover all natural numbers in the end.
 

Related Threads on Induction Proof

  • Last Post
Replies
6
Views
872
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
3
Replies
50
Views
6K
  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
1
Views
826
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
2
Views
888
Top