Mathematical Induction question

Question

This question should be done using either strong induction or weak induction.

If $111$ is a multiple of $3$

$111 111 111$ is a multiple of $9$

$111 1111111111111111111111$(to $n$) is a multiple of $3^n$

Prove this using induction

You have posted several questions now relatively close to each other, but haven't given your thoughts on any of them. This may make some users here more reluctant to help you. Please consider updating this post and the others with any thoughts and insights you might have towards the problem, even if it is just "I am really lost here." — Alex Wertheim, Jun 09 '13 at 18:09
The thing is I am really lost in most of the questions I have posted here . Next time I will post I am really lost . Thanks for the advise and helhp. — andrew, Jun 09 '13 at 21:30

score 0 · Answer 1 · edited Jun 09 '13 at 18:38

0

Let $$\underbrace{111\cdots 111}_{3^{n} }=3^{n}k$$

Then $$\underbrace{111\cdots 111}_{3^{n+1} } = 3^{n}k\cdot (10^{3^{n+1}-3^{n}}+10^{3^{n}}+1)$$

We have $$10^{m}\equiv 1 \pmod 3$$

Therefore,

$$10^{3^{n+1}-3^{n}}+10^{3^{n}}+1\equiv 1+1+1=3\pmod 3$$

Hence $$\underbrace{111\cdots 111}_{3^{n+1} } $$ is divisible by $3^{n}\cdot 3=3^{n+1}$

edited Jun 09 '13 at 18:38

Pedro

answered Jun 09 '13 at 18:19

Shaswata

score 0 · Answer 2 · answered Jun 09 '13 at 18:28

HINT:

Observe that $\underbrace{11...11}_{r \text{ terms }}=\frac{10^r-1}9$ where integer $r\ge1$

Let the highest power of $3$ in $\underbrace{11...11}_{3^m \text{ terms }}=\frac{10^{3^m}-1}9$ be $n$

So, $P(m)=10^{3^m}-1=9\cdot 3^n \cdot b$ where $(b,3)=1$

So, $P(m+1)=10^{3^{m+1}}-1=(10^{3^m})^3-1=(3^{n+2}b+1)^3-1\equiv0\pmod{3^{n+3}}$

Now, $P(1)=999\equiv0\pmod {3^{1+1}}$

2 Answers2