Mathematical Induction

1. Jan 10, 2006

forevergone

I have a problem when trying to prove n! >= 2^(n-1).

My work:

Assuming n=k, k! >= 2^k-1 (induction hypothesis).

To prove true for n=k+1,

(k+1)! >= 2^(k+1)-1 = 2^k

Now considering R.S., 2^k = (2^(k-1))(2)

I get stuck here. I don't know how to continue onwards to prove that (k+1)! is >= 2^k.

Can anyone show what I did wrong or what I should've done?

Last edited: Jan 11, 2006
2. Jan 10, 2006

HallsofIvy

First, You don't mean 2^k-1, you mean 2^(k-1). That is, the formula you want to prove is n!>= 2k-1, not n!>= 2k-1 (which is not true, for example, for n= 3).

Second, you didn't do the "base case": when n= 1, n!= 1 which is equal to 21-1= 2-1.

Third, assuming that k!>= 2^(k- 1), you don't know that (k+1)! >= 2^((k+1)-1)= 2^k . That's what you want to prove!

(k+1)!= (k+1)k! >= (k+1)(2k-1). Now what you need is to prove that (k+1)(2k-1) is larger than or equal to 2k. Perhaps you can do that with a separate induction proof.

3. Jan 11, 2006

Benny

k! >= 2^(k-1)
(k+1)k! >= (k+1)2^(k-1)
(k+1)! >= (k+1)2^(k-1)

You want a 2^k to appear on the RHS. You know that k is a natural number. It should be fairly easy to finish it off from there.

4. Jan 11, 2006

forevergone

Alright, thanks guys. I got it.

5. Jan 11, 2006

benorin

There's a simple way to do it without induction:

$$n!\geq 2^{n-1}\Rightarrow \ln (n!) = \sum_{k=1}^{n} \ln (k) \geq (n-1)\ln (2)$$

since $\ln(1)=0$ and $\ln(1)<\ln(2)<\ln(3)<\cdot\cdot\cdot<\ln(n-1)<\ln(n)$ it follows that

$$\sum_{k=1}^{n} \ln (k) = \sum_{k=2}^{n} \ln (k) > \sum_{k=2}^{n} \ln (2) \geq (n-1)\ln (2)$$

where the last inequality is not an equality for the sake of the n=1 case.