Proof by induction, ##(n)^{2} \le (2n)##.

[mikeyBoy83]

Homework Statement

I need to prove by induction that $(n!)^{2} \le (2n)!$. I'm pretty sure about my preliminary work, but I just need some suggestions for the end.

Homework Equations

It is well known from a theorem that if $a \le b$ and $c \ge 0$, then $ca \le cb$.

The Attempt at a Solution

ATTEMPT AT PROOF: For $n=1$, we can see that $(1!)^{2} \le (2\cdot 1)!$ holds. Now, assume that $(k!)^{2} \le (2k)!$ holds for $k \in N$. Then it must be shown that $n=k+1$ holds. For that,

$[(k+1)!]^{2} = (k+1)^{2}k!^{2}$ and by assumption $(k!)^{2} \le (2k)!$ implies with the theorem above that

$(k+1)^{2}k!^{2} \le (k+1)^{2}(2k)!$

And this is the point at which I don't know how to proceed. I need to conclude that this is in fact less than $[2(k+1)]!$, but I am unsure how to do that. I would appreciate any direction.

 

[Ray Vickson]

Homework Statement

I need to prove by induction that $(n!)^{2} \le (2n)!$. I'm pretty sure about my preliminary work, but I just need some suggestions for the end.

Homework Equations

It is well known from a theorem that if $a \le b$ and $c \ge 0$, then $ca \le cb$.

The Attempt at a Solution

ATTEMPT AT PROOF: For $n=1$, we can see that $(1!)^{2} \le (2\cdot 1)!$ holds. Now, assume that $(k!)^{2} \le (2k)!$ holds for $k \in N$. Then it must be shown that $n=k+1$ holds. For that,

$[(k+1)!]^{2} = (k+1)^{2}k!^{2}$ and by assumption $(k!)^{2} \le (2k)!$ implies with the theorem above that

$(k+1)^{2}k!^{2} \le (k+1)^{2}(2k)!$

And this is the point at which I don't know how to proceed. I need to conclude that this is in fact less than $[2(k+1)]!$, but I am unsure how to do that. I would appreciate any direction.

Are you absolutely required to use induction? I ask, because a direct proof (avoiding induction) is almost trivial.

 

[Orodruin]

What is $(2k)!/(2(k+1))!$ ?

 

[mikeyBoy83]

What is $(2k)!/(2(k+1))!$ ?

I assume you mean to use $(2(k+1))!/(2(k+1))!$ in which case the expression $\frac{(2k)!}{(2(k+1))!}$ is equivalent to $\frac{1}{2(k+1)(2k+1)}$, and so this reduces my inequality to

$(k+1)^{2}(k!)^{2} \le \frac{k+1}{2(2k+1)}\cdot (2(k+1))! \le (2(k+1))!$ since $\frac{k+1}{2(2k+1)} < 1$ for any $k\in N$. Is that what you had in mind?

 

[mikeyBoy83]

Are you absolutely required to use induction? I ask, because a direct proof (avoiding induction) is almost trivial.

I would prefer to use induction simply for the sake of practice. It is not required.

 

[Orodruin]

Is that what you had in mind?

Yes.

 

[PeroK]

$(k+1)^{2}k!^{2} \le (k+1)^{2}(2k)!$

And this is the point at which I don't know how to proceed. I need to conclude that this is in fact less than $[2(k+1)]!$, but I am unsure how to do that. I would appreciate any direction.

If you expand the factorials, I think you'll see it fairly obvious.

 

[mikeyBoy83]

If you expand the factorials, I think you'll see it fairly obvious.

Yes. You are right, thank you.