Mathematica Mathematical Induction

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:

HallsofIvy

Science Advisor
Homework Helper
41,682
864
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.
 
584
0
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.
 
Alright, thanks guys. I got it.
 

benorin

Homework Helper
1,060
8
There's a simple way to do it without induction:

[tex]n!\geq 2^{n-1}\Rightarrow \ln (n!) = \sum_{k=1}^{n} \ln (k) \geq (n-1)\ln (2)[/tex]

since [itex] \ln(1)=0[/itex] and [itex] \ln(1)<\ln(2)<\ln(3)<\cdot\cdot\cdot<\ln(n-1)<\ln(n)[/itex] it follows that

[tex]\sum_{k=1}^{n} \ln (k) = \sum_{k=2}^{n} \ln (k) > \sum_{k=2}^{n} \ln (2) \geq (n-1)\ln (2)[/tex]

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

Related Threads for: Mathematical Induction

Replies
3
Views
2K
Replies
5
Views
1K
Replies
7
Views
3K
Replies
0
Views
1K
Replies
4
Views
2K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top