# Divisibility via Induction: $8^n\mid (4n)!$ [duplicate]

I have to prove by induction the following fact:

Show that $(4n)!$ is divisible by $8^n$.

My stab at the solution:

I have a slightly bad feeling about this solution and I would like if someone would point me to my possible (more than likely) error(s).

Thank you,

Bayerischer

## marked as duplicate by N. F. Taussig, Daniel W. Farlow, Ross Millikan, barak manos, Daniel FischerApr 13 '16 at 18:45

• The solution looks fine whats the problem – Archis Welankar Apr 13 '16 at 7:27
• @ArchisWelankar, It seems too simple. I do not know whether my Inductive Hypothesis statement is written correctly. – Bayerischer Apr 13 '16 at 7:29

The most important part is the inductive step, where you said "Assume $8^n|(4n)!$ for all $n$" (for all $n\in\mathbb{N}$). The problem here is that you just assumed what you were trying to prove. Compare this statement to the original problem and you will find they are identical.

What we want to do is show that if $8^n|(4n)!$ for some $n\in\mathbb{N}$, then $8^{n+1}|(4(n+1))!$, and since our base case showed a natural number for which $8^n|(4n)!$ holds, we know via the principle of mathematical induction that it holds for all $n$ greater than your base case.

In order to show the first statement, let $8^n|(4n)!$ for some $n\in\mathbb{N}$. If we take a closer look at the assumption, $8^n|(4n)!$ for some $n\in\mathbb{N}$, what we're really saying is that $j8^n=(4n)!$ with $j\in\mathbb{N}$.

Now we want to show that $8^{n+1}|(4(n+1))!$ using our assumption, and really we're trying to show $k8^{n+1}=(4(n+1))!$ with $k\in\mathbb{N}$

Here, we must avoid saying $k8^{n+1}=(4(n+1))!$ right away, or else that would be another case of assuming what we're trying to prove. Instead, we start with one side and show that we can write it as the other. This part is pretty similar to your original proof.

$$(4(n+1))!=(4n+4)!=(4n+4)(4n+3)(4n+2)(4n+1)(4n)!$$

That part is totally fine if you were worried. It follow from the definition of factorial. In general, $n!=n(n-1)!=n(n-1)(n-2)!=...$ etc. More concretely, $8!=8\times 7!=8\times 7 \times 6!$ etc.

So we've shown $(4(n+1))!=(4n+4)(4n+3)(4n+2)(4n+1)(4n)!$ and we assumed $j8^n=(4n)!$ so we can substitute the $(4n)!$ in the first statement.

$(4(n+1))!=(4n+4)(4n+3)(4n+2)(4n+1)j8^n$, now we just need to find an extra 8 in that mess so we can have $8^{n+1}$. So multiply those factors out and then pull out an 8. Everything left over is an integer, and that's exactly what we wanted to show.

$(4(n+1))!=(4n+4)(4n+3)(4n+2)(4n+1)j8^n$ $(4(n+1))!=(256n^4+640n^3+560n^2+200n+24)j8^n$ $(4(n+1))!=(32n^4+80n^3+70n^2+25n+3)\times 8 \times j8^n$ $(4(n+1))!=(32n^4+80n^3+70n^2+25n+3)j8^{n+1}$

And since $(32n^4+80n^3+70n^2+25n+3)j$ is definitely a natural number, we can write it as some natural number $k\in\mathbb{N}$. Thus,

$(4(n+1))!=k8^{n+1}$ with $k\in\mathbb{N}$

which is what we wanted to show.

• You don't need to expand $(4n+1)(4n+2)(4n+3)(4n+4)$. It's equals to $(4n+1)2(2n+1)(4n+3)4(n+1) = 8 (4n+1)(2n+1)(4n+3)(n+1)$. – Orace Apr 13 '16 at 9:08
• For some reason, your first sentence appears three times. – N. F. Taussig Apr 13 '16 at 9:49

Step II.

This

Assume $8^n \vert (4n)!$ is true for all $n$

is absoultely WRONG. This is your theorem to prove — once you assume it is true, it became an axiom instead of a theorem.

Assume $8^n \vert (4n)!$ is true for some $n$

then show it implies that $8^{n+1} \vert (4(n+1))!$, consequently, based on the principle of induction, it is true for all $n$ equal or greater than the one, for which you checked manually.

Step III.

You have shown that if $F(n) = k\cdot 8^n$ then $F(n+1) = t\cdot F(n) = tk\cdot 8^n$ for some natural $k,t;$ but that's not enough. You need to show $8^{n+1}\vert F(n+1)$, that is $F(n+1) = k'\cdot 8^{n+1}$ for some natural $k',$ which means you need to demonstrate $8\vert t$ to complete the proof.

Added: To do that, note that $t$ is a product of four consecutive natural numbers. Two of them are even (divisible by $2$) and from those two one is divisible by $4$, hence the product is divisible by $8$.

In step II you say:

$8^n | F(n) => F(n)=8^v$

That's false. You should write.

$8^n | F(n) => F(n)=k*8^n$

So at step III you will have

$F(n+1)=t*F(n) => F(n+1) = t*k*8^n$

If you prove that $8|t$. (ie: $t = 8*t'$)

t = (4n+4)(4n+3)(4n+2)(4n+1)
= 4(n+1)(4n+3)2(2n+1)(4n+1)
= 8(n+1)(4n+3)(2n+1)(4n+1)
Hence 8|t

You will have: $F(n+1) = k*8*t'*8^n = k*t'*8^{(n+1)}$ hence $8^{(n+1)} | F(n+1)$ Q.E.D.

• Where did you get $t'$? – Bayerischer Apr 13 '16 at 7:38
• I add a spoil but it's the only soft difficulty here (apart from writing things down). – Orace Apr 13 '16 at 7:43

From the expression:

$(4n+4)(4n+3)(4n+2)(4n+1)[(4n)!]$

Note that by the I.H., $8^n|(4n)!$, thus we need only show that:

$8|(4n+4)(4n+3)(4n+2)(4n+1)$

Which we can do by factoring out common factors from the linear factors. Observe that $(4n+4)=4(n+1)$ and $(4n+2)=2(2n+1)$, hence we can rewrite

$(4n+4)(4n+3)(4n+2)(4n+1)$

as

$4(n+1)(4n+3)\cdot 2(2n+1)(4n+1)=8(n+1)(4n+3)(2n+1)(4n+1)$.

Thus $8^{n+1}|[4(n+1)]!$ as required.

• I do not know who to give the check-mark for correct answers. All of the answers provided have been correct. – Bayerischer Apr 13 '16 at 9:14
• Hehe, whichever answer you like the best (upvote all the ones you like too if you feel inclined) – Justin Benfield Apr 13 '16 at 9:15
• @Bayerischer a good rule can be first come, first served :) – Orace Apr 13 '16 at 9:43

First, show that this is true for $n=1$:

$(4\cdot1)!=8^1\cdot3$

Second, assume that this is true for $n$:

$(4n)!=8^nk$

Third, prove that this is true for $n+1$:

$(4(n+1))!=$

$(4n+4)!=$

$\color{red}{(4n)!}(4n+1)(4n+2)(4n+3)(4n+4)=$

$\color{red}{8^nk}(4n+1)(4n+2)(4n+3)(4n+4)=$

$8^nk(256n^4+640n^3+560n^2+200n+24)=$

$8^n(256n^4k+640n^3k+560n^2k+200nk+24k)=$

$8^{n+1}(32n^4k+80n^3k+70n^2k+25nk+3k)$

Please note that the assumption is used only in the part marked red.

• You don't need to expand $(4n+1)(4n+2)(4n+3)(4n+4)$. It's equals to $(4n+1)2(2n+1)(4n+3)4(n+1) = 8 (4n+1)(2n+1)(4n+3)(n+1)$. – Orace Apr 13 '16 at 9:07
• @Orace: It's just a different representation, and I've figured that it would be easier to explain this way. In fact, getting from your LHS to your RHS probably requires my expansion to begin with. – barak manos Apr 13 '16 at 9:21
• It's much more easier to see that $2|(4n+2)$ and $4|(4n+4)$ hence $8|t$ than expand a 4 part product with humongous factors. My comment, (and the spoil in my response) are straightforward. When your solution imply a lot of rigor for a trivial result. – Orace Apr 13 '16 at 9:40
• @Orace: But it takes a lot less explaining to simply expand that product. – barak manos Apr 13 '16 at 9:45
• I rewrite it from your post. $8^nk(4n+1)(4n+2)(4n+3)(4n+4)$ = $8^nk(4n+1)2(n+1)(4n+3)4(n+1)$=$8^{n+1}k(4n+1)(n+1)(4n+3)(n+1)$ There is 3 lines instead of 4 and I have no doubt about my factor. I can't even check your $540n^2$ by head. – Orace Apr 13 '16 at 9:51