$I(x_1, x_2, . . . , x_6) = 2x_1 + 4x_2 + 6x_3 + 8x_4 + 10x_5 + 12x_6 \mod 10$ is the invariant

Question

Each term in a sequence $1, 0, 1, 0, 1, 0, . . .$ starting with the seventh is the sum of the last $6$ terms $\mod 10$. Prove that the sequence $. . . , 0, 1, 0, 1, 0, 1, . . .$ never occurs.

Why $I(x_1, x_2, . . . , x_6) = 2x_1 + 4x_2 + 6x_3 + 8x_4 + 10x_5 + 12x_6 \mod 10$ is the invariant?

Answer 1

$$x_7\equiv x_1+x_2\dots x_6\mod10$$ $$\begin{align}2x_2+4x_3+6x_4+8x_5+10x_6+12x_7\equiv&2x_2+4x_3+6x_4+8x_5\\&+10x_6+12(x_1+x_2\dots x_6)\\\equiv&12x_1+14x_2+16x_3+18x_4+20x_5+22x_6\\ \equiv&2x_1+4x_2+6x_3+8x_4+10x_5+12x_6\end{align}$$

I dont have any motivation for this though. Maybe because of how $x_7$ is defined this is chosen

Answer 2

So you have a recurrence and you want an invariant which distinguishes $1,0,1,0,1,0$ from $0,1,0,1,0,1$, so your invariant will have to take into account six consecutive terms, and can't just be a variety of the sum, because the sum for both sequences is $3$.

You have $x_{n+1}=x_n+x_{n-1}+x_{n-2}+x_{n-3}+x_{n-4}+x_{n-5}$ and lets look for an invariant which is formed linearly so that $$I=ax_n+bx_{n-1}+cx_{n-2}+dx_{n-3}+ex_{n-4}+fx_{n-5}=ax_{n+1}+bx_n+cx_{n-1}+dx_{n-2}+ex_{n-3}+fx_{n-4}$$$$=(a+b)x_n+(a+c)x_{n-1}+(a+d)x_{n-2}+(a+e)x_{n-3}+(a+f)x_{n-4}+ax_{n-5}$$

Equating coefficients gives $a=a+b$ so that $b=0$, $b=a+c$ so that $c=-a$, $c=a+d$ so that $d=-2a$, $d=a+e$ so that $e=-3a$, $f=a+e$ so $f=-4a$ and $f=a$ so that $a=-4a$ and $5a=0$.

So you can't do this in the integers, but if you take a modulus for which $5a\equiv 0$ you have a chance - it could be mod $m=5$. Then $I=ax_{n+1}-ax_{n-1}-2ax_{n-2}-3ax_{n-3}-4ax_{n-4} \bmod m$

And for our two sequences we obtain the sums $-6a$ and $-3a$, so we could choose $a=1$ and modulus $5$ to distinguish them, but $a=2$ and $m=10$ also works.