Thorem: 2^n(n!)^2 <= (2n)!
Proof:
[I will use induction of the second form]
for n=1: 2^n(n!)^n = 2 = (2n)!
for n=2: 16 < 24
let us prove that the thorem satisfies n=k
(2n)!/n! = 2*6*...*(4n-2) [Note: this was proven in a previous excercise]
Hence:
(1) (2n)! = 2*6*...(4n-2)*n! = (1*3*...*(2n-1)) * 2^n * n! >= 2^n+(n!)^2 QED
Lemma 1
Every n >= 1 satisfies 1*3*...*(2n-1) >= n!
Proof:
for n=1: 1*1=1
for n=2: 1*3=2
Let us assume that n=k-1 satisfies the inequality and prove that this term is enough for n=k to satisfy it as well
Assumption: 1*3*...*(2[k-1]-1) >= (k-1)!
Theorem: 1*3*...*(2k-1) >= k!
Proof:
1*3*...*(2k-1) >= (k-1)!*(2k-1) [According to the assumption of the induction]
(k-1)!*(2k-1) = (k-1)! * 1*3*...*(2k-1)
k=1 satisfies 1=k=2k-1=1
k>1 satisfies k+1 < 2k ==> k < 2k+1
therefor (k-1)! * 1*3*...*(2k-1) >= (k-1)! * k * 1*3*...*(2k-3) = k! * 1*3*...*(2k-3) >= k!
Thus Lemma 1 is proved
Combining (1) and Lemma 1 we get that
(2n)! = (1*3*...*[2n-1])