Series Math Problem: Proving a_i - n_i is a Multiple of 7

[Icebreaker]

n_1 = 1

a_1 = 1

n_i = i

a_i = 8 a_{i-1} + 1

Is it possible to show that a_i - n_i is a multiple of 7 for all i > 1?

 

[selfAdjoint]

By my calculation, for i=2 you have a_2 = 8(a_1)+1 = 9, while n_2 = 2. So a_2 - n_2 = 7. And it just gets worse, since the a sequence is essentially geometric and the n sequence is arithmetic.

 

[Icebreaker]

Well, here are the first few values of this series:

n_i a_i
1 1
2 9
3 73
4 585
5 4681

 

[LeonhardEuler]

You can do a proof by induction. For your inductive step it will be useful to express a_{n-1} in a congruence mod 7.

 

[VietDao29]

First, you can do something like this in paper:
a_i = 8a_{i - 1} + 1 = 8(8a_{i - 2} + 1) + 1 = 8²a_{i - 2} + 8 + 1 = 8²(a_{i - 3} + 1) + 8¹ + 1 = 8³a_{i - 3} + 8² + 8¹ + 1 = 8⁴a_{i - 4} + 8³ + 8² + 8¹ + 1 = 8⁴a_{i - 4} + 8³ + 8² + 8¹ + 8⁰ (since 8⁰ = 1) ... and finally, you can relate a_i and a₁.
So a_i = 8^{i - 1}a_{i - (i - 1)} + 8^{i - 2} + 8^{i - 3} + ... + 8² + 8¹ + 8⁰ = 8^{i - 1}a₁ + 8^{i - 2} + 8^{i - 3} + ... + 8² + 8¹ + 8⁰ = 8^{i - 1} + 8^{i - 2} + 8^{i - 3} + ... + 8² + 8¹ + 8⁰ (Since a₁ = 1).
So you have:
a_i = \sum_{k = 0} ^ {i - 1} 8 ^ k (1), for all i >= 1.
This part helps you get the relation between a_i and i (but it's not a proof), then you can prove (1) by induction.
--------------
So a_i - i = \left( \sum_{k = 0} ^ {i - 1} 8 ^ k \right) - i.
Note that 8 \equiv 1 \mbox{ mod } 7.
So what can you say about: \sum_{k = 0} ^ {i - 1} 8 ^ k \equiv ? \mbox{ mod } 7
Viet Dao,

 

[Icebreaker]

I'll give it a shot.

 

[LeonhardEuler]

Actually, the problem is pretty simple. What you have to prove is that
a_n - n\equiv 0 mod7
or
a_n\equiv n mod7
You know that for n=2 this is true. Now suppose
a_{n-1}\equiv(n-1) mod 7
Then
a_n=8a_{n-1} +1 = 7a_{n-1} +a_{n-1} +1\equiv a_{n-1} +1mod7
It is easily taken from there to show that this is congruent to n.