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

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.
• Hint: $(4(n+1))! = (4n+4)! = (4n+4)(4n+3)(4n+2)(4n+1)(4n)! = 8(n+1)(4n+3)(2n+1)(4n+1) (4n)!$ – GohP.iHan Apr 12 '16 at 23:37
• You can also forego induction: Let $[x]$ denote the largest integer not exceeding $x.$ For prime $p$, the largest $k$ such that $p^k$ divides $n!$ is $k= \sum_{j=1}^n [n/p^j].$... Because $[n/p]$ counts how many multiples of $p$ are less or equal to $n$, and $[n/p^2]$ adds $1$ more for each multiple of $p^2$ not exceeding $n,$ and $[n/p^3]$ adds one more for......(etc). We have $\sum_{j=1}^n [4 n/2^j]\geq$ $[4 n/2^1+ 4 n/2^2]=$ $2 n +n=3 n.$ – DanielWainfleet Apr 13 '16 at 1:29

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}$.

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)!$?

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.