Divisibility via Induction: $8^n\mid (4n)!$

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Say instead:

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