Period of a binary sequence Given the first $5$ elements of a binary sequence $x_1 = 0, x_2 = 1, x_3 = 0, x_4 = 0, x_5 = 0$, the subsequent ones are determined as follows:
$$x_{n + 5} = x_{n} + x_{n + 2}$$
(this is an example of Linear Feedback Shift Register).
So,
$$01000010010110 \ldots$$
This sequence is periodic after $31$ elements. How is it possible to prove this?

$31 = 2^5 - 1$ and it can be related to the number of the first assigned elements $x_1, \ldots, x_5$.
I tried to expand the single items $x_i$ as a combination of the first $5$ items till no. $18$, with nothing relevant, except the fact that each $x_i$ can always be expressed as
$$x_i = a_1 x_1 + a_2 x_2 + a_3 x_3 + a_4 x_4 + a_5 x_5$$
where $a_i$ are integer coefficients.
Is this the right appoach to determine the periodicity of the sequence, or other ones are preferable?
 A: Your system can be described by the following matrix:
$$\left(\matrix{0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\\1&0&1&0&0\\}\right)\left(\matrix{x_n\\x_{n+1}\\x_{n+2}\\x_{n+3}\\x_{n+4}}\right)=\left(\matrix{\matrix{x_{n+1}\\x_{n+2}\\x_{n+3}\\x_{n+4}\\x_{n+5}}}\right)$$
Therefore all you need is to prove that the $31$st power of this matrix is the identity over $\mathbb{Z}_2$ (which is true, btw!).
A: The simple way to prove it is to compute the first $36$ terms and show that $01000$ recurs starting at position $32$ and not before.  As the length of the recurrence is $5$ the behavior is determined by five successive terms and you are done.  You can do the computation in a spreadsheet computing one term, then copy down for all the rest of the terms.
A: Any five subsequent elements determine the rest of the sequence, by the recursive formula. There are only $2^5 = 32$ such combinations of five elements possible, which means two things:


*

*The cycle, which inevitably occurs, will be at most of length $32$;

*The cycle will start occurring within $32$ steps.


The actual length of the cycle, and the point at which the cycle starts occurring, depends on the initial conditions: $x_i=0$ for all $i\in\{1\ldots 5\}$ gives a trivial sequence $00000\ldots$), for example. I don't know if there is any proper way, besides trial and error, to find the cycle length based on the initial conditions and the formula alone.
A: Your sequence of bits comes together with a matching generating function
$$
X(t)=x_0+x_1t+x_2t^2+\cdots=\sum_{i=0}^\infty x_it^i\in\Bbb{F}_2[[t]].
$$
Because all the arithmetic is done modulo two, the recurrency relation can be written to read $x_n+x_{n+2}+x_{n+5}=0$ for all $n\ge0$. The sum $x_n+x_{n+2}+x_{n+5}$ appears as the coefficient of $t^{n+5}$ the product
$
(1+t^3+t^5)X(t).
$ Check this yourself if you have never seen it, but this is really bread&butter in the theory LFSR-sequences. Consult e.g. Solomon Golomb's book.
Anyway, this means that all the terms of degree $5$ or higher in the product $X(t)(1+t^3+t^5)$ vanish. We therefore have the equation
$$
X(t)=\frac{A(t)}{1+t^3+t^5}\tag{1}
$$
for some polynomial $A(t)\in\Bbb{F}_2[t]$ of degree $\le4$.
Let's continue. Next I claim that the feedback polynomial $P(t)=1+t^3+t^5$ is irreducible in $\Bbb{F}_2[t]$. It is of degree five, so if it were reducible, then it would necessarily have a factor of degree at most two. But, $P(0)=P(1)=1$, so it has no zeros (and hence no linear factors). Nor is it divisible by the only irreducible quadratic polynomial $Q(t)=t^2+t+1$. This is because $Q(t)(t+1)=t^3+1$, so if $P(t)$ were divisible by $Q(t)$ so would be the monomial $t^5$, but that is absurd (by the uniqueness of factorization).
The basic properties of finite fields then tell us that


*

*the zeros of $P(t)$ are in the field $\Bbb{F}_{32}$ (aka $GF(32)$) and,

*therefore the zeros of $P(t)$ have multiplicative order that is a factor of $32-1=31$, and

*because $31$ is a prime (and $1$ is not a zero of $P(t)$), those zeros have order $31$ exactly.


Consequently $P(t)$ is a factor of the polynomial $t^{31}-1$. In many sources this fact is phrased as follows: the order of $P(t)$ is $31$. The argument outlined in the above sequence of bullets can be written using the concept of the order alone. I did it this way, because I think that on this site less people are familiat with that language.
Anyway, $P(t)R(t)=1-t^{31}$ for some polynomial $R(t)\in\Bbb{F}_2[t]$ of degree $31-5=26$. This allows us to rewrite $(*)$ as
$$
X(t)=\frac{A(t)R(t)}{1-t^{31}},\tag{2}
$$
where
$$
Q(t)R(t)=b_0+b_1tb_2t^2+\cdots b_{30}t^{30}\tag{3}
$$
is a polynomial of degree $\le30$.
By the familiar sum formula for the geometric series
$$
\frac1{1-t^{31}}=1+t^{32}+t^{2\cdot31}+t^{3\cdot31}+\cdots=\sum_{k=0}^\infty t^{k\cdot31}.\tag{4}
$$

Putting $(2),(3)$, and $(4)$ together we see that the coefficients of $X(t)$
  follow a repeating period of length 31. A single period can be read from the coefficients of the product $A(t)R(t)$.

A final remark. A user of a linear feedback shift register with this feedback polynomial $P(t)$ can adjust the coefficients of the polynomial $A(t)$ be initializing the LFSR with those coefficients. Some other readers would think of doing the same by declaring another initial segment $x_0,x_1,x_2,x_3,x_4$. All according to which sequence you want to produce. Actually, in this case all the $31$ non-zero initializations simply produce the $31$ cyclic shifts of the same $m$-sequence, but let's leave that for the specialists.
