# Induction Proof

1. Jan 13, 2009

### altcmdesc

I'm just wondering if this is a legitimate proof by induction.

Prove, for all natural numbers $$n$$, that $$2^n>n$$

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

We have:

$$2^{n-1}>n-1$$

$$2^n>2(n-1)=(n-1)+(n-1)>(n-1)+1=n$$

The last inequality follows from the fact that $$n>2$$.

I'm worried about the fact that I have more than one base case. Is this still alright?

Last edited: Jan 13, 2009
2. Jan 13, 2009

### mutton

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