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])