How do I show (2n)! >= 2^n((n!)^2) for every n>=0 by induction?
First we need to be clear how to construct a proof by induction. It has two main parts, the base case and the inductive step. Let P(n) denote that the statement is true for a fixed n. Our base case is to check that P(0) is true. Our inductive step is to show that if we assume P(n) is true, then we can derive that P(n+1) is true. This usually involves rearranging one side of P(n+1) untill we see one side of P(n) in some part of it then substituting the other side of P(n) and rearranging our way to the unseen side of P(n+1). Finally we must remember to conclude the proof, drawing together what we have shown to show the statement is true in general. The conclusion is pretty much the same for any proof of this type. The base case is simpler. Substitute n=0 into the LHS, then the RHS and check the inequality holds. To complete this part you need to make sure you understand the values of 20 and 0!. For the inductive step assume P(n). Write down this statement in full. Somewhere else write the statement for P(n+1) and remember it is our goal to derive this inquality. Starting with the LHS of P(n+1) argue your way to the RHS remembering to respect the inequality, so each new line should be greater or equal to the last. To complete this part it would be helpful to write out the meaning of some parts of the statement such as (2(n+1))! and (n+1)! 2. Our conclusion is that if P(n) is true then so is P(n+1), and since P(0) is true, the statement is true for evey integer n>=0.
