"Proof" that $(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$

Question

Please explain, as clearly as possible, what is wrong with the following "proof" by induction that

$\hspace{1.4 in}$$(2n)!$ is divisible by $2^n 5^{n-3}$ for $n\ge3$.

(There clearly must be an error, since the assertion is false for $n=6$.)

This is true for $n=3$:

$(2\cdot3)!=5\cdot18\cdot(2^3\cdot5^{3-3})$

Assume that this is true for $n$:

$(2n)!=5\cdot{k}\cdot\big(2^{n}\cdot5^{n-3}\big)$

Prove that this is true for $n+1$:

$(2(n+1))!= (2n+2)!=(2n+2)(2n+1)\color{blue}{(2n)!}$

$\hspace{.75 in}=2(n+1)(2n+1)\cdot\color{blue}{5\cdot k\cdot\big(2^n\cdot5^{n-3}\big)}$

$\hspace{.75 in}=(n+1)(2n+1)\cdot k\cdot\color{blue}{\big(2^{n+1}\cdot5^{(n+1)-3}\big)}$

Answer 1

You assume that $(2n)!$ can be written as $$5k(2^n\cdot5^{n-3})$$

Then you prove that $(2n+2)!$ can be written as $$k(2^{n+1}\cdot5^{n-2})$$

However, for the induction to hold, one needs to prove that $(2n+2)!$ can be written as $5k(2^{n+1}\cdot5^{n-2})$, because that is what you are assuming in the induction hypothesis.

Moral: Always write very clearly down what you are proving with the induction, and check whether that is what you are proving in the base case, hypothesis and induction step.

Answer 2

As Steven Stadnicki pointed out, the mistake in this argument is the presence of an extra factor of 5 in the induction hypothesis.

Since we are trying to show that $(2n)!$ is divisible by $2^n5^{n-3}$ for $n\ge3$,

in the induction hypothesis we want to assume that $n$ is an integer with $n\ge3$ such that

$\hspace{.2 in}(2n)!$ is divisible by $2^n5^{n-3}$, which implies that $\color{red}{(2n)!=k(2^n 5^{n-3})}$ for some integer $k$.

---

Notice that the presence of a factor of 5 in the base case does not affect the induction hypothesis, and that the induction step as given only shows that

if $(2n)!$ is divisible by $2^n 5^{n-2}$, then $(2n+2)!$ is divisible by $2^{n+1}5^{n-2}$.