Math Problem: Proving n! >= 2^(n-1) with Mathematical Induction

[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?

 

[HallsofIvy]

First, You don't mean 2^k-1, you mean 2^(k-1). That is, the formula you want to prove is n!>= 2^k-1, not n!>= 2^k-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 2¹-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)(2^k-1). Now what you need is to prove that (k+1)(2^k-1) is larger than or equal to 2^k. Perhaps you can do that with a separate induction proof.

 

[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.

 

[forevergone]

Alright, thanks guys. I got it.

 

[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.