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

  • #1
mikeyBoy83
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
2021 Award
19,544
9,912
What is ##(2k)!/(2(k+1))!## ?
 
  • #4
mikeyBoy83
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
mikeyBoy83
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
2021 Award
22,592
14,042
##(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
mikeyBoy83
21
1
If you expand the factorials, I think you'll see it fairly obvious.

Yes. You are right, thank you.
 

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

  • Last Post
Replies
4
Views
155
  • Last Post
Replies
7
Views
434
Replies
6
Views
221
  • Last Post
Replies
4
Views
564
Replies
4
Views
138
  • Last Post
Replies
2
Views
792
Replies
9
Views
207
  • Last Post
Replies
1
Views
897
  • Last Post
Replies
1
Views
275
Top