# Understanding mathematical induction for divisibility

I'm on my quest to understand mathematical induction proofs (beginners). First, thanks to How to use mathematical induction with inequalities? I kinda understood better the procedure, and practiced it with Is this induction procedure correct? ($2^n<n!$). It didn't turn out so bad :)

So far I've been doing equalities and inequalities. Alright. When things seemed to get better now I'm asked to prove divisibility.

My book has an exercise with the solution, but there is a part I don't get well:

With $n\ge1$ prove:

$n(n+1)(n+2)$ is divisible by 6.

Assume $$\exists k[n(n+1)(n+2) = 6k]$$ For the inductive step and using distribution: $$(n+1)(n+2)(n+3) = n(n+1)(n+2)+3(n+1)(n+2)$$ $$=6k+3\cdot2k'$$ $$=6(k+k') = 6k''$$

Alright. I see where is that $6k$ coming from, but what about the $3\cdot2k'$? How does the $3(n+1)(n+2)$ we had become that?

That's it for the example I didn't understand well. But I also tried doing another exercise by myself (and didn't manage to do it):

Prove, with $n\ge1$:

$10^n+3\cdot4^{n+2}+5$ is divisible by $9$.

First, I prove it for $n+1$:

To do so we need to show that $\exists x[10^1+3\cdot4^{1+2}+5=9x]$. It holds, because $(10^1+3\cdot4^{1+2}+5) = (10+3\cdot16+5) = (15+48) = 63 = 9 \cdot 7$

Now we assume $$\exists x[10^n+3\cdot4^{n+2}+5=9x]$$

We need to prove it for $n+1$: $$10^{n+1}+3\cdot4^{n+3} = 10^n\cdot10+3\cdot4^n\cdot4^3$$ $$= 10^n\cdot10+3\cdot4^{n+2}\cdot4$$ $$=(9x-3\cdot4^{n+2}-5)\cdot10+(3\cdot4^{n+2}\cdot4)$$ By this point I don't even know what I'm doing. I though that I could use $10^n$ with the inductive assumption and replace it with $(9x-3\cdot4^{n+2}-5)$, similar to what the book did before. But now the situation looks worse.

Similarly to this question How to use mathematical induction with inequalities?, I seek to understand mathematical induction when applied to divisibility cases this time. It seems (for me) that all these cases (equalities, inequalities and divisibility) do have important differences at the moment of solving.

-
Simply, either $n+1$ or $n+2$ is even, consequently, so are their product. – Berci Nov 27 '12 at 22:44
Compare to this question, which is the same problem, a little disguised math.stackexchange.com/questions/211121/… – Hendrik Jan Nov 27 '12 at 23:40

There is a simpler theorem of this type and that brings us the $2k'$: With $n\ge 1$ prove that $n(n+1)$ is amultiple of $2$.

Remark: You should now be able to prove with yet another induction that $\frac{(n+k)!}{(n-1)!}=n(n+1)\cdots (n+k)$ is a multiple of $k!$.

Your other attempt is fine so far. Note that $$(9x-3\cdot 4^{n+2}-5)\cdot 10+(3\cdot 4^{n+2}\cdot4) = 90x-18\cdot 4^{n+2}-50\\=9\cdot(10x-2\cdot 4^{n+2}-5)-5.$$

-
Question: In your last expression, there is a $-5$ hanging outside. Why is that okay to have? I mean, I though that the objective was to end up with something like $9x$ but now we have $9x-5$. Doesn't that cause problems? – Zol Tun Kul Nov 27 '12 at 23:22
That's probably because you started with $10^{n+1}+3\cdot 4^{n+3}$ instead of $10^{n+1}+3\cdot 4^{n+3}+5$. Thus the correct expression is divisible by $9$. – Hagen von Eitzen Nov 27 '12 at 23:29
Oh my... Damn it. You're right. – Zol Tun Kul Nov 27 '12 at 23:31

Do you agree that $\,a(b+c)=ab+ac\,$? Well, this is just what happened here:

$$(n+1)(n+2)(n+3)=[(n+1)(n+2)]\cdot n+[(n+1)(n+2)]\cdot 3$$

which is exactly what's written there.

Added: As for the other exercise:

$$10^{n+1}+3\cdot 4^{n+3}+5=10\cdot 10^n+4\cdot 3\cdot 4^{n+2}+5=$$

$$=\left(10^n+3\cdot 4^{n+2}+5\right)+9\cdot 10^n+3\cdot 3\cdot 4^{n+2}$$

and the first parentheses above is divisible by 9 by the inductive hypotheses, whereas the rest is obviously divisible by 9 as well!

-