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

• MHB
• lfdahl
In summary, the conversation discusses a sequence of integers modulo 11 defined by a recurrence relation. It is then shown that every such sequence is either constant or periodic with a period of 10. The participant, castor28, is thanked for their contribution and participation.
lfdahl
Gold Member
MHB
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$.

lfdahl said:
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$.
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$.

castor28 said:
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)

## 1. What is the purpose of proving the periodicity of a sequence?

The purpose of proving the periodicity of a sequence is to demonstrate that the sequence follows a repeating pattern and can be described by a finite set of terms. This can help in making predictions and understanding the behavior of the sequence.

## 2. How do you determine the period of a sequence?

The period of a sequence is the number of terms in the repeating pattern. To determine the period, you can observe the sequence and look for the point at which the terms start to repeat. This can also be done by using mathematical techniques such as finding the greatest common divisor or using modular arithmetic.

## 3. What is the significance of using modular arithmetic in proving periodicity?

Modular arithmetic allows us to look at the remainder when dividing the terms of a sequence by a specific number. In the case of proving periodicity, we use modular arithmetic to see if the remainders follow a repeating pattern. If they do, then the sequence is periodic.

## 4. Can you give an example of a sequence that is not periodic?

Yes, the sequence 1, 2, 3, 4, 5, 6, ... is not periodic because it continues infinitely without repeating. It does not follow a specific pattern or have a finite set of terms.

## 5. How does proving the periodicity of a sequence relate to the study of number theory?

The study of number theory involves understanding the properties and patterns of numbers. Proving the periodicity of a sequence uses number theory concepts such as modular arithmetic and divisibility. It also helps in finding relationships between the terms of a sequence and exploring the properties of numbers within the sequence.

Replies
1
Views
10K
Replies
7
Views
1K
Replies
11
Views
3K
Replies
4
Views
2K
Replies
1
Views
949
Replies
125
Views
17K
Replies
1
Views
1K
Replies
0
Views
321
Replies
17
Views
3K
Replies
1
Views
1K