Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$

Question

Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$

So far I have: Base case (n = 1) = $8^{1} | (4(1))!$

= $8 | 24$ which is true.

Induction Step:

$8^{n + 1} | (4(n + 1))!$

$8^{n + 1} | (4n + 4)!$

• A bit confused as to how to close this proof out, also wanted to make sure my current progress is correct as well. Any help is appreciated.

Answer 1

Well, you know that $(4n)! = 8^nk$ for some integer $k$.

$$\Rightarrow (4n + 4)! = (4n+4)(4n+3)(4n+2)(4n+1)(4n)!$$ $$ = 8^nk(4n+4)(4n+3)(4n+2)(4n+1)$$

Factor out of the even terms: $$ = 8^n 8 k (n+1)(4n+3)(2n+1)(4n+1)$$ $$= 8^{n+1} k'$$

For some integer $k'$. This means that $(4n+1)!$ is divisible by $8^{n+1}$.

Answer 2

Good so far, to finish up just note that $$(4(n + 1))! = (4n + 4)! = (4n + 4)(4n + 3)(4n + 2)(4n + 1)(4n)!.$$ Since $4$ divides $(4n + 4)$ and $2$ divides $(4n + 2$), we have that $8$ divides $(4n + 4)(4n + 3)(4n + 2)(4n + 1)$. By the induction hypothesis, $8^n$ divides $(4n)!$. Therefore $8^{n+1}$ divides $(4(n + 1))!$, completing the induction step.

You can also prove this statement without induction. Let $S = \{1,2\ldots,4n\}$. Note that there are $2n$ multiplies of $2$ in $S$ and $n$ multiplies of $4$ in $S$. Can you see why this implies that $2^{2n} \cdot 2^n = 2^{3n} = 8^n$ divides $(4n)!$?

Answer 3

Use the fact for any integer $n$, one of the numbers inside $n,n+1,n+2,n+3$ divisible by $4$ and one of them is divisible by $2$ but not $4$.

This easy fact says us any $4$ consecutive integers divisible by $8$.

We will use this fact in induction step.