Induction proof that $n! > n^3$ for $n \ge 6$, and $\frac{(2n)!}{n! 2^n}$ is an integer for $n \ge 1$

Question

Prove by induction that

(a) $n! > n^3$ for every $n \ge 6$.

(b) prove $\frac{(2n)!}{n!2^n}$ is an integer for every $n\geq 1$

I'm quite terrible with induction so any help would be appreciated.

Answer 1

(a) $n! > n^3$ for every $n \geq 6$

For the induction base, we simple have to show that $6! \geq 6^3$. Hence, $6 * 5 * 4 * (3 * 2) * 1 \geq 6*6*6$. Hence $6 * 6 * (5 * 4) \geq 6^3$. This is evidently true, as $5*4 = 20 > 6$.

For the induction step, we have to show that $(n+1)! \geq (n+1)^3$ for $n\geq 6$. Now suppose $n! > n^3$ is true for all $n \geq 6$. Then $(n+1)! = (n+1)n! \geq (n+1)n^3$.

Hence, we are done if $(n+1)n^3 \geq (n+1)^3$ for $n\geq 6$. Thus, we need to show that $n^4 + n^3 \geq n^3 + 3n^2 + 3n + 1$ for $n\geq 6$.

Rearranging yields $n^4 - 3n^2 - 3n - 1 \geq 0$ for $n\geq 6$. The second derivative of this is $12n^2 - 6$, which is strictly convex for $n\geq 6$. Hence, we are through if both $f(n) := n^4 - 3n^2 - 3n - 1 \geq 0$ and $f'(n) = 4n^3 -6n - 3 \geq 0$ for $n=6$. This is trivial to check.

(b) $\frac{(2n)!}{n! 2^n}$ is an integer for every $n\geq 1$.

The induction base is trivial: simply insert $n=1$.

For the induction step, we need to show that $\frac{(2(n+1))!}{(n+1)^2 2^{n+1}} = \frac{(2n+2)!}{(n+1)n! * 2 * 2^n} = \frac{(2n+2)(2n+1)}{2(n+1)} * \frac{(2n)!}{n! 2^n}$ is an integer for all $n\geq 1$.

Now, by the induction hypothesis, the right multiplicand must be an integer. Hence, it suffices to show that the left multiplicand must be an integer as well. Since $(2n+2) = 2(n+1)$, this is obviously the case.

Answer 2

In part b, you have an interesting expression. What we will prove there is that $$\frac{(2n)!}{n!2^n}=1\times 3\times 5\times\cdots \times 2n-1,$$ the product of the first $n$ odd numbers.

Base case: $\frac{(2\times1)!}{1!2^1}=1$.

This tells us that when we plug $n=1$ into the above equation, we get the result of multiplying the first odd number, $1$.

Inductive step:

We first state the inductive hypothesis. This is that $$\frac{(2n-2)!}{(n-1)!2^{n-1}}=1\times 3\times 5\times\cdots\times 2n-3.$$ Now we compute $$\frac{(2n)!}{n!2^n}=\frac{2n(2n-1)}{2n}\frac{(2n-2)!}{(n-1)!2^{n-1}}=(2n-1)\frac{(2n-2)!}{(n-1)!2^{n-1}}=\\ 1\times 3\times 5\times\cdots\times 2n-3\times 2n-1,$$ which is he product of the first $n$ odd numbers, which is in fact an integer.

Note that we have proved a bit more than you wanted. Note that this is essentially the same proof that Martin gave, except we are keeping track of a little bit more. Note only did we prove the expression to be an integer, we describe what the integer is in a nice way. This should tell us that when we prove something by induction, it behooves us to look at it closely to see if we can squeeze more information out of the proof. A nice exercise is to find an expression for the first $n$ even numbers.