Periodic sequence

In mathematics, a periodic sequence (sometimes called a cycle or orbit) is a sequence for which the same terms are repeated over and over:

a₁, a₂, ..., a_p,  a₁, a₂, ..., a_p,  a₁, a₂, ..., a_p, ...

The number p of repeated terms is called the period (period).<ref name=":0">Template:Eom </ref>

Definition

A (purely) periodic sequence (with period p), or a p-periodic sequence, is a sequence a₁, a₂, a₃, ... satisfying

a_n+p = a_n

for all values of n.<ref name=":0" /><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref name=":2">Template:Cite journal</ref> If a sequence is regarded as a function whose domain is the set of natural numbers, then a periodic sequence is simply a special type of periodic function.Template:Citation needed The smallest p for which a periodic sequence is p-periodic is called its least period<ref name=":0" /> or exact period.

Examples

Every constant function is 1-periodic.

The sequence <math>1,2,1,2,1,2\dots</math> is periodic with least period 2.

The sequence of digits in the decimal expansion of 1/7 is periodic with period 6:

<math>\frac{1}{7} = 0.142857\,142857\,142857\,\ldots</math>

More generally, the sequence of digits in the decimal expansion of any rational number is eventually periodic (see below).<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

The sequence of powers of −1 is periodic with period two:

<math>-1,1,-1,1,-1,1,\ldots</math>

More generally, the sequence of powers of any root of unity is periodic. The same holds true for the powers of any element of finite order in a group.

A periodic point for a function Template:Math is a point Template:Mvar whose orbit

<math>x,\, f(x),\, f(f(x)),\, f^3(x),\, f^4(x),\, \ldots</math>

is a periodic sequence. Here, <math>f^n(x)</math> means the Template:Nowrap composition of Template:Mvar applied to Template:Mvar. Periodic points are important in the theory of dynamical systems. Every function from a finite set to itself has a periodic point; cycle detection is the algorithmic problem of finding such a point.

Partial sums and products

<math>\sum_{n=1}^{kp+m} a_{n} = k*\sum_{n=1}^{p} a_{n} + \sum_{n=1}^{m} a_{n}, \qquad \prod_{n=1}^{kp+m} a_{n} = \biggl({\prod_{n=1}^{p} a_{n}}\biggr)^k \cdot \prod_{n=1}^{m} a_{n}</math>,

where <math>m < p</math> and <math>k</math> are positive integers.

Periodic 0, 1 sequences

Any periodic sequence can be constructed by element-wise addition, subtraction, multiplication and division of periodic sequences consisting of zeros and ones. Periodic zero and one sequences can be expressed as sums of trigonometric functions:

<math>\sum_{k=0}^0 \cos \left(2\pi\frac{nk}{1}\right)/1 = 1,1,1,1,1,1,1,1,1, \cdots</math>

<math>\sum_{k=0}^{1} \cos \left(2\pi\frac{nk}{2}\right)/2 = 1,0,1,0,1,0,1,0,1,0, \cdots</math>

<math>\sum_{k=0}^{2} \cos \left(2\pi\frac{nk}{3}\right)/3 = 1, 0,0,1,0,0,1,0,0,1,0,0,1,0,0, \cdots</math>

<math>\cdots</math>

<math>\sum_{k=0}^{N-1} \cos \left(2\pi\frac{nk}{N}\right)/N = 1,0,0,0,\cdots,1, \cdots

\quad \text{sequence with period } N </math>

One standard approach for proving these identities is to apply De Moivre's formula to the corresponding root of unity. Such sequences are foundational in the study of number theory.

Generalizations

A sequence is eventually periodic or ultimately periodic<ref name=":0" /> if it can be made periodic by dropping some finite number of terms from the beginning. Equivalently, the last condition can be stated as <math>a_{k+r} = a_k</math> for some r and sufficiently large k. For example, the sequence of digits in the decimal expansion of 1/56 is eventually periodic:

1 / 56 = 0 . 0 1 7  8 5 7 1 4 2  8 5 7 1 4 2  8 5 7 1 4 2  ...

A sequence is asymptotically periodic if its terms approach those of a periodic sequence. That is, the sequence x₁, x₂, x₃, ... is asymptotically periodic if there exists a periodic sequence a₁, a₂, a₃, ... for which

<math>\lim_{n\rightarrow\infty} x_n - a_n = 0.</math><ref name=":2" />

For example, the sequence

1 / 3,  2 / 3,  1 / 4,  3 / 4,  1 / 5,  4 / 5,  ...

is asymptotically periodic, since its terms approach those of the periodic sequence 0, 1, 0, 1, 0, 1, ....