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

In summary, the given statement ##(n!)^{2} \le (2n)!## can be proved by using induction and the given theorem, as shown in the attempt at a solution. The final step in the induction proof is to show that ##(k+1)^{2}(2k)! \le (2(k+1))!##, which can be easily verified by expanding the factorials.
  • #1
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.
 
Physics news on Phys.org
  • #2
mikeyBoy83 said:

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
What is ##(2k)!/(2(k+1))!## ?
 
  • #4
Orodruin said:
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
Ray Vickson said:
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.
 
  • #6
mikeyBoy83 said:
Is that what you had in mind?
Yes.
 
  • #7
mikeyBoy83 said:
##(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.
 
  • Like
Likes mikeyBoy83
  • #8
PeroK said:
If you expand the factorials, I think you'll see it fairly obvious.

Yes. You are right, thank you.
 

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

What is proof by induction?

Proof by induction is a mathematical proof technique used to prove statements involving natural numbers. It involves proving that a statement is true for a base case, typically n=1, and then showing that if the statement is true for some value of n, it must also be true for n+1. This allows us to conclude that the statement is true for all natural numbers.

How is proof by induction useful?

Proof by induction is useful for proving statements that involve an infinite number of cases, such as statements involving natural numbers. It allows us to prove these statements in a concise and systematic way, without having to consider each individual case.

What is the statement ##(n)^{2} \le (2n)##?

The statement ##(n)^{2} \le (2n)## is an inequality involving the natural number n. It states that for any natural number n, the square of n is less than or equal to twice n. This statement can be used to prove various mathematical theorems and can also have practical applications in fields such as computer science.

How do you prove ##(n)^{2} \le (2n)## using induction?

To prove ##(n)^{2} \le (2n)## using induction, we first establish the base case by showing that the statement is true for n=1. Then, we assume that the statement is true for some arbitrary value of n, and use this assumption to prove that it is also true for n+1. This completes the inductive step and allows us to conclude that the statement is true for all natural numbers.

Can proof by induction be used to prove other types of statements?

Yes, proof by induction can be used to prove other types of statements, not just those involving natural numbers. It can also be used to prove statements about sets, graphs, and other discrete structures. However, it is most commonly used for statements involving natural numbers due to its efficiency and effectiveness in these cases.

Similar threads

Induction with binomial coefficient
Replies
15
Views
2K
Proof that a recursive sequence converges
Replies
5
Views
2K
Each integer n>11 can be written as the sum of two composite numbers?
Replies
7
Views
3K
Show |x^2 sin^8(e^x)| <= (16 pi^3)/3
Replies
7
Views
3K
Real Analysis: Prove Upper Bound of Sum of Bounded Sequences
Replies
6
Views
1K
Induction Proof, Apostol Calc Vol I, I.4.4.7
Replies
6
Views
1K
Lower Central Series - Understanding the Induction Process
Replies
4
Views
1K
Show operator is compact/symmetric
Replies
5
Views
2K
Eigenvalue of matrix proof by induction
Replies
7
Views
520
Proof by mathematical induction
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top