Prove by induction that $36,306,3006,30006$ is divisible by 18

Question

Hi I'm quite new to induction so I don't really know how I should tackle this problem.

I took out a calculator and checked the results

2,16,167,1667 I sort of see a pattern but how would I start the induction?

Always divisible by $9$ (why?) and what more? – Piquito Feb 03 '16 at 01:43 — Piquito, Feb 03 '16 at 01:43

score 1 · Accepted Answer · answered Feb 03 '16 at 01:15

HINT: Let $a_n$ be the number of this form with $n$ zeroes in the middle, so that $a_0=36$, $a_1=306$, and so on.

Once you’ve done that, showing by induction on $n$ that $a_n$ is always divisible by $18$ should be pretty straightforward.

score 1 · Answer 2 · answered Feb 03 '16 at 01:36

1

A number is divisible by $18$ iff it is even and is divisible by $9$.

Now $3000\cdots006$ is clearly even and is divisible by $9$ because the sums of its digits is $9$.

answered Feb 03 '16 at 01:36

lhf

score 0 · Answer 3 · answered Feb 03 '16 at 01:25

Each of those numbers can be expressed in the form $3(10^{n})+6$.

As you have already demonstrated, it is true for the case $n=1$.

Assume it holds for some natural number $k$ so that for $n=k$:

18|$3(10^{k})+6$.

Now for $n=k+1$ we have:

$3(10^{k+1})+6= 30(10^{k})+6=[3(10^{k})+6]+27(10^{k})=[3(10^{k})+6]+27(2^{k})(5^{k})=[3(10^{k})+6]+18(3)(2^{k-1})(5^{k})$

Since both of the last two terms are divisible by 18, the inductive proof is complete.

3 Answers3