1
$\begingroup$

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.
$\endgroup$
2
  • 3
    $\begingroup$ 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)! $ $\endgroup$
    – GohP.iHan
    Apr 12, 2016 at 23:37
  • $\begingroup$ 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.$ $\endgroup$
    – DanielWainfleet
    Apr 13, 2016 at 1:29

3 Answers 3

Reset to default
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.