MHB Sequence Challenge: Proving Periodicity of $\left\{x_n\right\}$ (Mod 11)

[lfdahl]

Let the sequence $\left\{x_n\right\}$ of integers (modulo $11$) be defined by the recurrence
relation:

$x_{n+3} \equiv \frac{1}{3}(x_{n+2}+x_{n+1}+x_n)$ (mod $11$), for $n=1,2,..$

Show, that every such sequence $\left\{x_n\right\}$ is either constant or periodic with period $10$.

 

[castor28]

Let the sequence $\left\{x_n\right\}$ of integers (modulo $11$) be defined by the recurrence
relation:

$x_{n+3} \equiv \frac{1}{3}(x_{n+2}+x_{n+1}+x_n)$ (mod $11$), for $n=1,2,..$

Show, that every such sequence $\left\{x_n\right\}$ is either constant or periodic with period $10$.

Spoiler

Since we are working modulo $11$, I understand that $\frac{1}{3}$ means $4$.

This is a linear recurrence relation, whose characteristic polynomial is:

$$x^3 - 4x^2 - 4x - 4$$
​

Modulo $11$, this polynomial factors as:

$$(x-1)(x-6)(x-8)$$
​

and this means that the general solution is:

$$x_n = A(1)^n + B(6)^n + C(8)^n\pmod{11}$$
​

where the constants depend on the initial terms. If $B=C=0$, the sequence is constant; otherwise, since both $6$ and $8$ have multiplicative order $10$ modulo $11$, the sequence has period $10$.

 

[lfdahl]

Spoiler

Since we are working modulo $11$, I understand that $\frac{1}{3}$ means $4$.

This is a linear recurrence relation, whose characteristic polynomial is:

$$x^3 - 4x^2 - 4x - 4$$
​

Modulo $11$, this polynomial factors as:

$$(x-1)(x-6)(x-8)$$
​

and this means that the general solution is:

$$x_n = A(1)^n + B(6)^n + C(8)^n\pmod{11}$$
​

where the constants depend on the initial terms. If $B=C=0$, the sequence is constant; otherwise, since both $6$ and $8$ have multiplicative order $10$ modulo $11$, the sequence has period $10$.

Thankyou, castor28!, for your sharp minded contribution and participation, which is highly appreciated!(Yes)