How do I prove that if $n$ is greater or equal to $4$, then $(2n)!$ is greater than or equal to $10^n$?

Question

I used the method of induction to prove this.

For the basis step, when $n=4$, the statement is $[2(4)]!≥10^4$ which is the same as $40320≥10000$ which is true.

Next, for the inductive step, we show $\mathrm{S}_k$ implies $\mathrm{S}_{k+1}$ for some integer $n=k≥1$.

By assuming that $(2k)!≥10^k$ is true. Therefore, we need to show $(2k+2)!≥10^{k+1}$ for $n=k+1$. First, $10^{k+1}=10\cdot10^k$. By the induction hypothesis, $(2k)!≥10^k$, so $10\cdot(2k)!≥10\cdot10^k$.

Since $k≥4$, we know that $2(k+1)≥10$. So, $2(k+1)\cdot(2k)!≥10\cdot10^k$ by substitution. This simplifies to $(2(k+1))!≥10\cdot10^k$ which equals $(2(k+1))!≥10^{k+1}$ which we needed to show.

I know my expansion from $2(k+1)(2k)!$ to $(2(k+1))!$ is wrong, but I don't know what the correct way to get to $(2(k+1))!$ from $2(k+1)(2k)!$.

Answer 1

Assuming $(2n)! \geq 10^n$,

For your induction step -

$(2n+2)!\geq 10^{n+1} \,$ or $\, (4n^2+6n+2)\frac{(2n)!}{10^n} \geq 10$

Is true if $\, (4n^2+6n+2)\geq 10$ (which seems obvious for $n \geq 1$)

Or you can go on as below,

i.e. if $\, 2n^2 + 3n - 4 \geq 0 \implies n \geq \frac{\sqrt41}{4} - \frac{3}{4}$

i.e. if $n\, \geq 1$, which is true.

Answer 2

Alternative proof without induction:

Firstly, if $n=4, (2n)! = 8! = 40320 > 10^4 = 10^n$.

If $n\ge 5$, note that $$\forall 1\le i \le n, i(2n+1-i)=2n + (i-1)(2n-i) \ge 2n \ge 10.$$ Therefore $$(2n)! = \underset{i=1}{\overset{n}{\Pi}} \left[i(2n+1-i)\right] \ge 10^n. \blacksquare$$

Answer 3

With induction but more clear:

You have proved the base case, so let's continue.

Let $(2n)!\ge 10$. Then: $$(2(n+1))!=(2n+2)!=(2n+2)(2n+1)(2n)!=(4n^2+6n+2)(2n)!\ge (4n^2+6n+2)\cdot 10^n$$

Clearly $4n^2+6n+2 \ge 10$ for $n \ge 1$ so: $$(2(n+1))! \ge (4n^2+6n+2)\cdot 10^n \ge 10\cdot 10^n=10^{n+1}$$ $$(2(n+1))! \ge 10^{n+1}$$ And we have proved the inductive step $\blacksquare$

Just to clarify, you were actually almost there. We know that $2(k+1)\cdot (2k)! = (2k+2) \cdot (2k)! \le (2k+2)(2k+1) \cdot (2k)! = (2(k+1))!$

If $2(k+1)\cdot (2k)! \ge 10^{k+1}$ and $(2(k+1))! \ge 2(k+1)\cdot (2k)!$ then $(2(k+1))! \ge 10^{k+1}$