# Proving that a sequence is periodic

Given the following sequence,

$$1,1,2,3,5,8,3,1,4,5,9,4,3,7....$$ $$a_{n+2}=(a_n+a_{n+1}) \mod{10}\;\;\;\; \forall\;\;{n\geq{1}}$$ Prove that it is periodic?

My Attempt:

There can be atmost $10 \times 10=100$ unique pairs of integers $(a,b)$ with $0\leq{a,b}\leq9$.

So pairs will certainly start repeating after $100$ pairs.

Let the first pair repeating after $100$ is $(x,y)$.

The problem I am facing is that how can prove that $(x,y)$ will have unique predecessors and successors, i.e., if $$...a,b,x,y,c,d...\in\text{sequence}$$

also,

$$...e,f,x,y,g,h... \in \text{sequence}$$

then , $a=e,b=f,c=g,d=h...$

If I can prove this, I can easily prove that $(x,y)$ will trace back to $(1,1)$ and the sequence is periodic.

Any hints on how I can show this.

Also let me know if I can make the question more clearer.

• Abstract duplicate of math.stackexchange.com/a/872077/44121 Aug 14 '18 at 12:29
• This question makes no sense. You can't prove that a sequence is periodic if you haven't defined it. Aug 14 '18 at 12:36
• If your sequence has $b,x,y$ as consecutive terms then $y\equiv x+b\pmod {10}$ so you can solve for $b\pmod {10}$ given $x,y$.
– lulu
Aug 14 '18 at 12:37
• Wikipedia says the period is $60$.
– lhf
Aug 14 '18 at 12:40
• In this case the series is periodic from the start because the recurrence relation also works backwards. Aug 14 '18 at 12:47

First of all, when you say that the sequence follows the rule that you specify just by looking at its first entries, you are making a guess ... a reasonable guess, of course, but a guess nevertheless.

Anyway, let's just say that the rule you indicate does indeed specify the sequence we are interested in. Is it periodic?

Your observation that given that the number of pairs of numbers is finite, and hence that there has to be a repeat of some a pair of numbers at some point is correct.

However, there is no need to worry about the predecessors: once you have a repeat of $x,y$ in your sequence, then, given the rule, from then on everything will be the same again, and that is all you need to show it is cyclic.

In fact, there are many sequences that are cyclic, but where the cycle is preceded by a little 'start-up' that does not get repeated ... i.e. where its graph looks like a '6', not a '0'. For such sequences, you would not be able to prove that the predecessors are always the same as well, because that would not be true. But, you still have that cycle, and that makes it periodic.

In sum, the sequence will be periodic, though it may not go back to $(1,1)$

That said, it is actually easy to show that the sequence will go back to $(1,1)$, for all the predecessors will be the same: if you have

$$b,x,y$$

and

$$f,x,y$$

then it must be the case that

$$b+ x =y \mod 10$$

and

$$f+x=y \mod 10$$

and from that it immediately follows that $b=x$ given that $0 \le b,f \le 9$

Once you have established that $b=f$ it likewise follows that $a=e$ ... but you really don't need to show that anymore: once you have shown the immediate predecessor of two numbers is fixed, then all predecessors are fixed. In short, from any $a_n$ and $a_{n+1}$, both $a_{n+2}$ and $a_{n-1}$ are fully determined.