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

  • #1
21
1

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.
 

Answers and Replies

  • #2
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,722

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.
 
  • #3
Orodruin
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
Gold Member
17,253
7,074
What is ##(2k)!/(2(k+1))!## ?
 
  • #4
21
1
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?
 
  • #5
21
1
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.
 
  • #7
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
17,575
9,340
##(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.
 
  • #8
21
1
If you expand the factorials, I think you'll see it fairly obvious.

Yes. You are right, thank you.
 

Related Threads on Proof by induction, ##(n!)^{2} \le (2n)!##.

  • Last Post
Replies
9
Views
4K
  • Last Post
Replies
2
Views
639
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
6
Views
872
  • Last Post
Replies
18
Views
3K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
4
Views
3K
Top