How Can You Prove That n! Is Greater Than 2^n for n > 3?

[tamtam402]

Homework Statement

I'm self-studying Boas book (Mathematical methods in the physical sciences) and one of the problems asks me to prove that for n > 3, n! > 2^n

Homework Equations

There isn't really any "equations".

The Attempt at a Solution

My english is bad so I'll try to explain properly.

I wrote down both series and I can see that with n!, for n > 3 you multiply the previous expression by n to get the next term, but for 2^n every term is simply the last one multiplied by 2. Sorry if the words aren't used correctly but you should see where I'm getting at. However, how do I show this mathematically? Any help would be appreciated!

 

[micromass]

Hi tamtam402!

Mathematically, we often use induction to show this. Have you seen how to do a proof by induction?

 

[Ray Vickson]

Homework Statement

I'm self-studying Boas book (Mathematical methods in the physical sciences) and one of the problems asks me to prove that for n > 3, n! > n^2

Homework Equations

There isn't really any "equations".

The Attempt at a Solution

My english is bad so I'll try to explain properly.

I wrote down both series and I can see that with n!, for n > 3 you multiply the previous expression by n to get the next term, but for n^2 every term is simply the last one multiplied by 2. Sorry if the words aren't used correctly but you should see where I'm getting at. However, how do I show this mathematically? Any help would be appreciated!

Your statement that "for n^2 every term is simply the last one multiplied by 2" is false. We do not get 3^2 = 9 by multiplying 2^2 = 4 by 2!

RGV

 

[tamtam402]

Your statement that "for n^2 every term is simply the last one multiplied by 2" is false. We do not get 3^2 = 9 by multiplying 2^2 = 4 by 2!

RGV

My bad! I meant 2^n. As for proofs by induction, I haven't been taught how to do that. Would you mind giving me an example with my question or something similar if possible? Thanks!

 

[micromass]

Check out http://en.wikipedia.org/wiki/Mathematical_induction
Specifically, the sections Description and Example are interesting.

I'll give another example that is more related to your problem. I will try to prove the Bernouilli inequality, which states

$$(1+x)^n\geq 1+nx$$

for all natural numbers n.

First, we prove the base case, that is we prove the inequality for n=0. This is trivial since

$$(1+x)^0=1~\text{and}~1+0x=1$$

so the inequality is satisfied for n=0 (and is actually an equality here).

For the induction step, we accept that the theorem is true for n-1 (that is: $(1+x)^{n-1}\geq 1+(n-1)x$ holds and is called the induction hypothesis), and we prove it for n.
So, we do:

$$(1+x)^n=(1+x)^{n-1}(1+x)\geq (1+(n-1)x)(1+x)=1+x+(n-1)x+(n-1)x^2=1+nx+(n-1)x^2\geq 1+nx$$

where we have used the induction hypothesis for the first inequality. The second inequality follows from the fact that $(n-1)x^2\geq 0$ always holds.

 

[hunt_mat]

One way that you could do is a brute force attempt. n!=n*(n-1)*...*2*1, then examine n!/2^n which gives:
$$\frac{n!}{2^{n}}=\frac{n}{2}\frac{n-1}{2}\frac{n-2}{2}\cdots\frac{3}{2}\frac{2}{2}\frac{1}{2}$$
Now for what n is this greater than one?

 

[tamtam402]

Check out http://en.wikipedia.org/wiki/Mathematical_induction
Specifically, the sections Description and Example are interesting.

I'll give another example that is more related to your problem. I will try to prove the Bernouilli inequality, which states

$$(1+x)^n\geq 1+nx$$

for all natural numbers n.

First, we prove the base case, that is we prove the inequality for n=0. This is trivial since

$$(1+x)^0=1~\text{and}~1+0x=1$$

so the inequality is satisfied for n=0 (and is actually an equality here).

For the induction step, we accept that the theorem is true for n-1 (that is: $(1+x)^{n-1}\geq 1+(n-1)x$ holds and is called the induction hypothesis), and we prove it for n.
So, we do:

$$(1+x)^n=(1+x)^{n-1}(1+x)\geq (1+(n-1)x)(1+x)=1+x+(n-1)x+(n-1)x^2=1+nx+(n-1)x^2\geq 1+nx$$

where we have used the induction hypothesis for the first inequality. The second inequality follows from the fact that $(n-1)x^2\geq 0$ always holds.

Thanks, I'm currently reading the wikipedia entry. Shouldn't you have proved this for n+1 instead of n-1 though?

 

[Kreizhn]

For the induction step, it doesn't really matter whether you prove it for n, n-1, or n+1, so long as your induction hypothesis is 1 less or you're using strong induction.

 

[micromass]

Shouldn't you have proved this for n+1 instead of n-1 though?

It's the same thing if you think about it. I proved that the statement for n-1 implies the statement for n. But this is the same thing as proving that the statement for n implies the statement for n+1.

The idea of induction is "falling dominoes". If you prove that "the first stone will drop" and "if the n'th stone drops then the n+1'th stone drops", then all stones will drop. Indeed, the first stone drops because of the hypothesis. The second stone drops because the first stone drops and the hypothesis. The third stone drops because the second stone drops and the hypothesis,...

But note, if I've written "if the n-1'th stone drops then the n'th stone drops", this would give me the exact same results...