0
$\begingroup$

I am self-studying Discrete Mathematics (in Portuguese), and there is one exercise I was not able to solve.

Show that the number $111\ldots 1$ (formed by $3^{n}$ digits are equal to $1$) is divisible by $3^{n}.$

All I was able to do was to show the base case, but I do not know how to use the inductive step.

I would appreciate your help.

  • 0
    @spohreis: No worries.2012-03-23

3 Answers 3

3

Hint $\ $ By below, $\rm\:\ 3^k\: |\: f_n\ \Rightarrow\ 3^{k+1}\: |\: f_{n+1}.\:$ Yours is the special case $\rm\:c = 3.$ $\rm\displaystyle\ f_n = \frac{(3c\!+\!1)^{3^n}\!-1}{3c}\ \ \Rightarrow\ \ f_{n+1} = \frac{(3c\:\!f_n\! +\! 1)^3-1}{3c}\: =\: \frac{9c\:f_n\:\!m}{3c}\: =\: 3\:f_n m $

8

I think you meant

For $n\geq 1$ Show that the number $111 \cdots 1$ (formed by $3^n$ 1's) is divisible by $3^n$.

Base case is clear.Denote let $A_m:= \underbrace{111 \cdots 1}_{3^m}$. Suppose the result is true for integers $n=k$, then $A_{k+1}= \frac{10^{3^{k+1}}-1}{9}=\frac{(10^{3^k})^3-1}{9}=\frac{10^{3^k}-1}{9}(10^{2\cdot3^n}+10^{3^n}+1)=A_k\times S$

where $S=10^{2\cdot3^n}+10^{3^n}+1$, since $S$ is a multiple of $3$ the conclusion follows.

4

I’m sure that you meant to say that the number was formed by $3^n$ digits equal to $1$, not $3^3$ digits.

Let $m_n$ be the number whose decimal representation is a string of $3^n$ $1$’s. To be explicit, $m_n=\frac19(10^{3^n}-1)$. Suppose that $3^n$ divides $m_n$ for some $n$, say $m_n=3^nk$. Then $\begin{align*} m_{n+1}&=10^{3^n}\left(10^{3^n}m_n+m_n\right)+m_n\tag{1}\\ &=\left(10^{2\cdot3^n}+10^{3^n}+1\right)m_n\\ &=\left(10^{2\cdot3^n}+10^{3^n}+1\right)3^nk\;, \end{align*}$

and we need only show that $3$ divides $10^{2\cdot3^n}+10^{3^n}+1$. But $10\equiv 1\pmod 3$, so every power of $10$ is congruent to $1$ mod $3$, and therefore $10^{2\cdot3^n}+10^{3^n}+1$ is indeed a multiple of $3$.

If the step $(1)$ is a little puzzling at first, look at an example:

$m_2=111111111=111000000+111000+111=1000(1000m_1+m_1)+m_1\;.$