How to write this proof by induction

Question

Prove by Induction √(2n)! <2^n * n!, n≥1, n∈ℕ.

Hi I am looking for how to write the proof to this, and I only recently started to study induction proofs, so an extra explanation or annotations along the way are very appreciated. thanks if anyone can help.

Answer 1

A good saying that comes along with proofs by induction is:

"Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step)."

- Concrete Mathematics, Page 3

Let S(n) be the statement as follows for all 1 ≤ n ∈ ℕ:

S(n): √(2n)! < 2^n * n!

Here is a proof by induction on n.

Base Case: Show that S(n) is true for the smallest value of n, in this case 1.

S(1) : √(2(1))! < 2^(1) * (1)!

√2 < 2

Hence S(1) is clearly true since √2 < 2

Induction Step: Show that for every k ≥ 1, if S(k) is true, then S(k+1) also holds.

√(2k)! < 2^k * k!

(2k)! < 2^2k * (k!)^2 Square both sides

(2k+2)(2k+1)(2k)! < 2^2k * (2k+2)(2k+1)(k!)^2 multiply both sides by (2k+2)(2k+1)

(2k+2)(2k+1)(2k)! < 2^(2k+1) * (k+1)(2k+1)(k!)^2 Pull out a 2 from the (2k+2) and absorb into 2^2k

(2k+2)! < 2^(2k+2) * (k^2 +1.5k+0.5)(k!)^2

1. foil out (k+1)(2k+1), pull out another 2, and put it into the exponent

(2k+2)! < 2^(2k+2) * [ (k+1)^2 - 0.5(k+1) ] (k!)^2

1. Here I completed the square to get a (k+1)^2 out of the foiled out (2k+2)(2k+1) terms, It doesn't look pretty now but trust me...

(2k+2)! < 2^(2k+2) * [ (k+1)^2 ] (k!)^2

1. Here we can drop the 0.5(k+1) term because it only diminishes the term in the brackets. That is, it only makes the term in the brackets smaller, so if we drop the diminishing term we know it will still remain larger than (2k+2)!

(2k+2)! < 2^(2k+2) * (k+1)!^2 Absorb the (k+1)^2 term into the factorial

√(2k+2)! < 2^(k+1) * (k+1)! Square root both sides

√(2(k+1))! < 2^(k+1) * (k+1)!

That is, statement S(k+1) also holds true.

Conclusion: Since both the base case and the induction step have been established as true, by mathematical induction the statement S(n) holds for all 1 ≤ n ∈ ℕ.

Note: sorry if I cluttered my answer with too much explanation... i wanted to walk through each step to make sure everything makes sense. Thanks for the fun problem! I haven't done a proof by induction in quite some time! Let me know if you have any issues or if you notice any mistakes :)

Answer 2

sqr(2n!) < 2^n)(n!)

let n= 1

sqr(2(1)!) < 2^1)(1!)

sqr2 < 2

let n=2

sqr(4!) < 2^2)(2!)

sqr(24) < 4(2)

2sqr6 <8

assume it's true for n=k

sqr(2k!) < 2^k)(k!)

try to show

sqr(2(k+1)!) < 2^(k+1)(k+1)!

sqr(2k!(k+1)) < 2^k)(2)(k+1)k!

sqr(2k!)sqr(k+1)< 2(2^k)k!(k+1)

since sqr(2k!)< (2^k)k!

and

sqr(k+1) <2(k+1), that's the product of two factors on the left side < product of 2 factors on the right side

that's sort of the basic approach,

a start anyway

check with another tutor for a more rigorous proof, with luck they'll post something, soon

play with the k+1 inequality and try to rewrite it to mimic the k inequality that you assumed is true

hard to believe this is an algebra 2 problem, it's at least college algebra level