Is this a valid proof for n >2^n for all n>3

[Battlemage!]

Homework Statement

Show that n!>2ⁿ for all n>3.

Homework Equations

I will attempt to use induction.

The Attempt at a Solution

We want to show that n!>2ⁿ for all n>3.
Consider the case when n=4.
4! = 24 > 2^4 =16.

We want to show by way of induction that if the inequality is true for some k greater than 4, it is true for k+1.

Assume the inequality holds for k>4. Then,
2^k < k!
2*2^k < 2k!
2^{k+1} < 2k!
for k>4.

But 2k! < (k+1)! for all k>4. Therefore

2^{k+1} &lt; (k+1)!

and so by induction it follows that n! > 2ⁿ for all n > 3.

 

[micromass]

Proof is ok, but I'm going to be annoying:

Assume the inequality holds for k>4. Then,
2^k &lt; k!
2*2^k &lt; 2k!

Why?

2^{k+1} &lt; 2k!
for k>4.

Why?

But 2k! < (k+1)! for all k>4.

Why?

 

[Battlemage!]

Proof is ok, but I'm going to be annoying:

Thank you. That always helps.

Why?

The reason I assumed it held for k>4: 4 is the very first integer greater than 3. I figured if I can establish by induction that it holds for 4, then 5, 6, 7,...k, k+1,... then it must hold for all numbers greater than 3. There is no upper bound on k. I did spin my wheels a bit at first since I'm used to the base case being k=1.

As for the second part, I multiplied by 2 because that would allow me to easily get the k+1 case because the base for the power is 2, and x^ax = x^a+1. (also I don't believe the way everything relates to the number 2 here is coincidental. I think there might be a deeper relation between the base of the power and when it is larger than the factorial).

Why?

Because I multiplied both sides by a positive integer, so the inequality should remain. The multiplication was done so I can get the k+1 case for the exponent. I then kind of lucked into the next part. I knew I had to get to some point where the left was less than the target quantity, and this worked out well.

Why?

Because:
\lim_{n\rightarrow ∞ } \frac{2n!}{(n+1)!} = 0
*EDIT I had n approaching zero for some reason

and as for k =3,2,1 and 0, I manually tested them. k>4 is overkill for this part. But I figured that in order remain consistent I'd stick with k >4, since it is necessary for comparing the exponential to the factorial.

 

[member 587159]

\lim_{n\rightarrow 0} \frac{2n!}{(n+1)!} = 0

This is wrong.

 

[PeroK]

Homework Statement

Show that n!>2ⁿ for all n>3.

Homework Equations

I will attempt to use induction.

The Attempt at a Solution

We want to show that n!>2ⁿ for all n>3.
Consider the case when n=4.
4! = 24 &gt; 2^4 =16.

We want to show by way of induction that if the inequality is true for some k greater than 4, it is true for k+1.

Assume the inequality holds for k>4. Then,
2^k &lt; k!
2*2^k &lt; 2k!
2^{k+1} &lt; 2k!
for k>4.

But 2k! < (k+1)! for all k>4. Therefore

2^{k+1} &lt; (k+1)!

and so by induction it follows that n! > 2ⁿ for all n > 3.

There is, however, a small but significant error in your original proof. This is not related to insufficient justification, but is a genuine flaw.

Big hint: what happened to the case $n = 5$? Where did you cover that?

 

[Battlemage!]

This is wrong.

I wrote it wrong. It's supposed to be as n approaches infinity.

 

[micromass]

I wrote it wrong. It's supposed to be as n approaches infinity.

That means that for all $\varepsilon>0$, there is an $N$ such that if $n>N$ we have $2n! <\varepsilon (n+1)!$.

Your claim is that for all $n>3$ we have $2n!<(n+1)!$. Those are very distinct statements.

 

[Battlemage!]

That means that for all $\varepsilon>0$, there is an $N$ such that if $n>N$ we have $2n! <\varepsilon (n+1)!$.

Your claim is that for all $n>3$ we have $2n!<(n+1)!$. Those are very distinct statements.

Oh I see what you're saying.

For that part when I answered your why question by posting the limit I just meant that because I knew that limit was zero it led me to the idea of trying to set up an inequality where

2^k+1 < 2k! < (k+1)! for k>4.

I did not actually give a mathematical reason haha. I will think on it and try to articulate a better one.

 

[Ray Vickson]

Homework Statement

Show that n!>2ⁿ for all n>3.

Homework Equations

I will attempt to use induction.

The Attempt at a Solution

We want to show that n!>2ⁿ for all n>3.
Consider the case when n=4.
4! = 24 &gt; 2^4 =16.

We want to show by way of induction that if the inequality is true for some k greater than 4, it is true for k+1.

Assume the inequality holds for k>4. Then,
2^k &lt; k!
2*2^k &lt; 2k!

If you mean $2 \times 2^k < (2k)!$ then that does not follow from the previous line. If you mean $2 \times 2^k < 2 \times k!$ then that does follow.

 

[SammyS]

There is, however, a small but significant error in your original proof. This is not related to insufficient justification, but is a genuine flaw.

Big hint: what happened to the case $n = 5$? Where did you cover that?

@Battlemage!

PeroK's question has been ignored. It raises an important point!

 

[Battlemage!]

If you mean $2 \times 2^k < (2k)!$ then that does not follow from the previous line. If you mean $2 \times 2^k < 2 \times k!$ then that does follow.

Yes that's what I meant. I figured a factorial was only grouped with other terms if there were parentheses, but then again it's not like a factorial is in PEMDAS so I would be ignorant of such rules.

@Battlemage!

PeroK's question has been ignored. It raises an important point!

I post these questions at work and unfortunately ran out of time. I was thinking about it, though. Sadly I'm at a loss. More information below...

There is, however, a small but significant error in your original proof. This is not related to insufficient justification, but is a genuine flaw.

Big hint: what happened to the case $n = 5$? Where did you cover that?

Okay... let me see...

I have manually tested 5 and it works. 5! = 120 >2⁵ = 32.
Likewise with my last step, 2⁵ = 32 < 2(5!) = 240 < (5+1)! = 6! = 720.

As for the induction process, I've never done it where the base case wasn't one. Did I do it wrong with my base case of 4?Since I included k greater than 4, doesn't that already include 5. I don't quite understand what you're getting at. Any other hints? :/

EDIT- since we're here, I did find a different way to do it working the other way.

(k +1)! = (k + 1)k! &gt; (k + 1)2^k
and since k > 4 then
(k + 1)! &gt; 2^k * 2
(k + 1)! &gt; 2^{k+1}

 

[PeroK]

As for the induction process, I've never done it where the base case wasn't one. Did I do it wrong with my base case of 4?

Since I included k greater than 4, doesn't that already include 5. I don't quite understand what you're getting at. Any other hints? :/

What you did was:

a) Showed it was true for $n = 4$

b) Showed that if it was true for $k > 4$ it was true for $k+1$

But, $k > 4$ starts at $k =5$. So, you didn't cover the step $P(k = 4) \ \Rightarrow \ \ P(k = 5)$.

The inductive stage of your proof should have been for $k \ge 4$.

On the other issues, I think you have let the questions confuse you and over-elaborated your answers. Your proof depended only on (if $a, b$ are positive):

$a < b \ \Rightarrow \ 2a < 2b$

And

$k > 2 \ \Rightarrow \ 2a < ka$

You must see this, but recognising these simple facts and stating them simply and mathematically is something that generally does not seem to come naturally to many people.

On a final point, I would tend to write either $2(k!)$ or $(2k)!$ to avoid any ambiguity. Like you, I don't know what PEMDAS has to say about factorials.

 

[Battlemage!]

What you did was:

a) Showed it was true for $n = 4$

b) Showed that if it was true for $k > 4$ it was true for $k+1$

But, $k > 4$ starts at $k =5$. So, you didn't cover the step $P(k = 4) \ \Rightarrow \ \ P(k = 5)$.

The inductive stage of your proof should have been for $k \ge 4$.

So essentially if I replace the > with a ≥ that would fix the issue?

On the other issues, I think you have let the questions confuse you and over-elaborated your answers. Your proof depended only on (if $a, b$ are positive):

$a < b \ \Rightarrow \ 2a < 2b$

And

$k > 2 \ \Rightarrow \ 2a < ka$

You must see this, but recognising these simple facts and stating them simply and mathematically is something that generally does not seem to come naturally to many people.

So I could have omitted this part?

But 2k! < (k+1)! for all k>4.

On a final point, I would tend to write either $2(k!)$ or $(2k)!$ to avoid any ambiguity. Like you, I don't know what PEMDAS has to say about factorials.

Yeah I think I'll do that from now on.

I appreciate the help by the way.

 

[PeroK]

So essentially if I replace the > with a ≥ that would fix the issue?

Yes, but you should see that yourself.

So I could have omitted this part?

There was nothing you could have omitted. You just needed to justify what you were doing a little more.