SOLUTION: Let a_n = 11...1 with 3^n digits. Prove that a_n is divisible by 3a

SOLUTION: Let a_n = 11...1 with 3^n digits. Prove that a_n is divisible by 3a_(n-1).

Question 389515: Let a_n = 11...1 with 3^n digits. Prove that a_n is divisible by 3a_(n-1).
Found 2 solutions by richard1234, robertb:
Answer by richard1234(7193) (Show Source): You can put this solution on YOUR website!
We have

, etc.

Proceed by induction. The base case n = 1 works, as 111 is divisible by 3.

For some ,

Then, for k+1,

It suffices to show that is an integer. Substituting , we obtain:

Letting , we have

Rearrange the terms:

The last term is equivalent to the numerator in the fraction we wish to prove is an integer. Therefore, we can substitute this expression and obtain

(we are trying to prove this is an integer for all k)

Cancel out z from both sides to get

It now suffices to prove that the numerator is divisible by 3, which happens if and only if is divisible by 3. However, we already know that which is divisible by 3, since all powers of 10 are 1 modulo 3 (therefore subtracting 1 makes it 0 mod 3, i.e. divisible by 3). Hence, the expression is an integer, and we are done.

This is a somewhat lengthy proof, but rigorous proofs are sometimes more efficient and strong in terms of explaining their points. You'll definitely see proofs like this in contests like USAMO, IMO, and Putnam.
Answer by robertb(5830) (Show Source): You can put this solution on YOUR website!
a_1 = 111 =
a_2 = 111 111 111 =
a_3 = 111 111 111...111 (27 1's) =
........
a_n = by induction.
Then, substituting 999 for .

Now is definitely a positive integer, because the numerator is a positive integer with digits, of which are 0's, and 3 are 1's. Hence the sum of the digits of the numerator is 3, which makes the number itself divisible by 3.

RELATED QUESTIONS
please help me with this use the method of mathematical induction to prove the following (answered by math-vortex)
Prove that n^3 + (n+1)^3 + (n+2)^3 is divisible by 9 for all n in Natural numbers. I... (answered by aaaaaaaa,mathslover)
prove that 【(n+1)^n】+1 is divisible by n^2 by using binomial theorem (answered by Shin123)
Prove using math induction 2^n + (-1)^n+1 is divisible by... (answered by math_helper)
Prove that the value of the expression is not divisible by 6 for any whole n:... (answered by MathLover1,greenestamps)
Show that one out of n,n+3,n+6,n+9 is divisible by n when n is a natural number? (answered by solver91311)
Let a, b, n ∈ Z with n > 1. Prove that if a ≡ b (mod n) then 2a ≡ 2b... (answered by jim_thompson5910)
prove that: 1+2+3+....+n =... (answered by ikleyn)
if n is apositive integer prove that (1+1/n+1)^n >... (answered by vleith)