Series math problem

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$$?

Last edited by a moderator:

Staff Emeritus
Gold Member
Dearly Missed
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
Gold Member
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
Homework Helper
First, you can do something like this in paper:
ai = 8ai - 1 + 1 = 8(8ai - 2 + 1) + 1 = 82ai - 2 + 8 + 1 = 82(ai - 3 + 1) + 81 + 1 = 83ai - 3 + 82 + 81 + 1 = 84ai - 4 + 83 + 82 + 81 + 1 = 84ai - 4 + 83 + 82 + 81 + 80 (since 80 = 1) ... and finally, you can relate ai and a1.
So ai = 8i - 1ai - (i - 1) + 8i - 2 + 8i - 3 + ... + 82 + 81 + 80 = 8i - 1a1 + 8i - 2 + 8i - 3 + ... + 82 + 81 + 80 = 8i - 1 + 8i - 2 + 8i - 3 + ... + 82 + 81 + 80 (Since a1 = 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 ai 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,

Last edited:
Icebreaker
I'll give it a shot.

LeonhardEuler
Gold Member
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.