Periodic sequence

Last updated May 30, 2024

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

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.^[1]^[2]^[3] 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.^{[ citation needed ]} The smallest p for which a periodic sequence is p-periodic is called its least period^[1] or exact period.

Examples

Every constant function is 1-periodic.

The sequence $1,2,1,2,1,2\dots$ is periodic with least period 2.

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

{\frac {1}{7}}=0.142857\,142857\,142857\,\ldots

More generally, the sequence of digits in the decimal expansion of any rational number is eventually periodic (see below).^[4]

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

-1,1,-1,1,-1,1,\ldots

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 $f : X \to X$ is a point $x$ whose orbit

x,\,f(x),\,f(f(x)),\,f^{3}(x),\,f^{4}(x),\,\ldots

is a periodic sequence. Here, $f^{n}(x)$ means the $n$ -fold composition of $f$ applied to $x$ . 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.

Identities

Partial Sums

\sum _{n=1}^{kp+m}a_{n}=k*\sum _{n=1}^{p}a_{n}+\sum _{n=1}^{m}a_{n}

Where k and m<p are natural numbers.

Partial Products

\prod _{n=1}^{kp+m}a_{n}=({\prod _{n=1}^{p}a_{n}})^{k}*\prod _{n=1}^{m}a_{n}

Where k and m<p are natural numbers.

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:

\sum _{k=1}^{1}\cos \left(-\pi {\frac {n(k-1)}{1}}\right)/1=1,1,1,1,1,1,1,1,1,\cdots

\sum _{k=1}^{2}\cos \left(2\pi {\frac {n(k-1)}{2}}\right)/2=0,1,0,1,0,1,0,1,0,\cdots

\sum _{k=1}^{3}\cos \left(2\pi {\frac {n(k-1)}{3}}\right)/3=0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,\cdots

\cdots

\sum _{k=1}^{N}\cos \left(2\pi {\frac {n(k-1)}{N}}\right)/N=0,0,0,\cdots ,1,\cdots \quad {\text{sequence with period }}N

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^[1] if it can be made periodic by dropping some finite number of terms from the beginning. Equivalently, the last condition can be stated as $a_{k+r}=a_{k}$ 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

\lim _{n\rightarrow \infty }x_{n}-a_{n}=0.

^[3]

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, ....

Related Research Articles

In mathematics, the arithmetic–geometric mean of two positive real numbers $x$ and $y$ is the mutual limit of a sequence of arithmetic means and a sequence of geometric means. The arithmetic–geometric mean is used in fast algorithms for exponential, trigonometric functions, and other special functions, as well as some mathematical constants, in particular, computing $π$ .

In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers $n \geq k \geq 0$ and is written $It is the coefficient of the x k term in the polynomial expansion of the binomial power (1 + x) n; this coefficient can be computed by the multiplicative formula$

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency. The interval at which the DTFT is sampled is the reciprocal of the duration of the input sequence. An inverse DFT (IDFT) is a Fourier series, using the DTFT samples as coefficients of complex sinusoids at the corresponding DTFT frequencies. It has the same sample-values as the original input sequence. The DFT is therefore said to be a frequency domain representation of the original input sequence. If the original sequence spans all the non-zero values of a function, its DTFT is continuous, and the DFT provides discrete samples of one cycle. If the original sequence is one cycle of a periodic function, the DFT provides all the non-zero values of one DTFT cycle.

In mathematics, the trigonometric functions are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all sciences that are related to geometry, such as navigation, solid mechanics, celestial mechanics, geodesy, and many others. They are among the simplest periodic functions, and as such are also widely used for studying periodic phenomena through Fourier analysis.

In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor series are equal near this point. Taylor series are named after Brook Taylor, who introduced them in 1715. A Taylor series is also called a Maclaurin series when 0 is the point where the derivatives are considered, after Colin Maclaurin, who made extensive use of this special case of Taylor series in the 18th century.

<span class="mw-page-title-main">Simplex</span> Multi-dimensional generalization of triangle

In geometry, a simplex is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. For example,

In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on. In a finite continued fraction, the iteration/recursion is terminated after finitely many steps by using an integer in lieu of another continued fraction. In contrast, an infinite continued fraction is an infinite expression. In either case, all integers in the sequence, other than the first, must be positive. The integers $are called the coefficients or terms of the continued fraction.$

<span class="mw-page-title-main">Fourier series</span> Decomposition of periodic functions into sums of simpler sinusoidal forms

A Fourier series is an expansion of a periodic function into a sum of trigonometric functions. The Fourier series is an example of a trigonometric series, but not all trigonometric series are Fourier series. By expressing a function as a sum of sines and cosines, many problems involving the function become easier to analyze because trigonometric functions are well understood. For example, Fourier series were first used by Joseph Fourier to find solutions to the heat equation. This application is possible because the derivatives of trigonometric functions fall into simple patterns. Fourier series cannot be used to approximate arbitrary functions, because most functions have infinitely many terms in their Fourier series, and the series do not always converge. Well-behaved functions, for example smooth functions, have Fourier series that converge to the original function. The coefficients of the Fourier series are determined by integrals of the function multiplied by trigonometric functions, described in Common forms of the Fourier series below.

In mathematics, the error function, often denoted by $erf$ , is a function defined as:

In mathematics, the Gibbs phenomenon is the oscillatory behavior of the Fourier series of a piecewise continuously differentiable periodic function around a jump discontinuity. The $th partial Fourier series of the function produces large peaks around the jump which overshoot and undershoot the function values. As more sinusoids are used, this approximation error approaches a limit of about 9% of the jump, though the infinite Fourier series sum does eventually converge almost everywhere except points of discontinuity.$

<span class="mw-page-title-main">Digamma function</span> Mathematical function

In mathematics, the digamma function is defined as the logarithmic derivative of the gamma function:

In signal processing, a finite impulse response (FIR) filter is a filter whose impulse response is of finite duration, because it settles to zero in finite time. This is in contrast to infinite impulse response (IIR) filters, which may have internal feedback and may continue to respond indefinitely.

The Basel problem is a problem in mathematical analysis with relevance to number theory, concerning an infinite sum of inverse squares. It was first posed by Pietro Mengoli in 1650 and solved by Leonhard Euler in 1734, and read on 5 December 1735 in The Saint Petersburg Academy of Sciences. Since the problem had withstood the attacks of the leading mathematicians of the day, Euler's solution brought him immediate fame when he was twenty-eight. Euler generalised the problem considerably, and his ideas were taken up more than a century later by Bernhard Riemann in his seminal 1859 paper "On the Number of Primes Less Than a Given Magnitude", in which he defined his zeta function and proved its basic properties. The problem is named after Basel, hometown of Euler as well as of the Bernoulli family who unsuccessfully attacked the problem.

In mathematics, the discrete-time Fourier transform (DTFT) is a form of Fourier analysis that is applicable to a sequence of discrete values.

<span class="mw-page-title-main">Stieltjes constants</span>

In mathematics, the Stieltjes constants are the numbers $that occur in the Laurent series expansion of the Riemann zeta function:$

In mathematics, Mathieu functions, sometimes called angular Mathieu functions, are solutions of Mathieu's differential equation

In number theory, Ramanujan's sum, usually denoted c_q(n), is a function of two positive integer variables q and n defined by the formula

In the 1760s, Johann Heinrich Lambert was the first to prove that the number $π$ is irrational, meaning it cannot be expressed as a fraction $, where and are both integers. In the 19th century, Charles Hermite found a proof that requires no prerequisite knowledge beyond basic calculus. Three simplifications of Hermite's proof are due to Mary Cartwright, Ivan Niven, and Nicolas Bourbaki. Another proof, which is a simplification of Lambert's proof, is due to Miklós Laczkovich. Many of these are proofs by contradiction.$

<span class="mw-page-title-main">Dirichlet kernel</span> Concept in mathematical analysis

In mathematical analysis, the Dirichlet kernel, named after the German mathematician Peter Gustav Lejeune Dirichlet, is the collection of periodic functions defined as

References

1 2 3 4 "Ultimately periodic sequence", Encyclopedia of Mathematics , EMS Press, 2001 [1994]
↑ Bosma, Wieb. "Complexity of Periodic Sequences" (PDF). www.math.ru.nl. Retrieved 13 August 2021.
1 2 Janglajew, Klara; Schmeidel, Ewa (2012-11-14). "Periodicity of solutions of nonhomogeneous linear difference equations". Advances in Difference Equations. 2012 (1): 195. doi: 10.1186/1687-1847-2012-195 . ISSN 1687-1847. S2CID 122892501.
↑ Hosch, William L. (1 June 2018). "Rational number". Encyclopedia Britannica. Retrieved 13 August 2021.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[:0-1] 1 2 3 4 "Ultimately periodic sequence", Encyclopedia of Mathematics , EMS Press, 2001 [1994]

[2] Bosma, Wieb. "Complexity of Periodic Sequences" (PDF). www.math.ru.nl. Retrieved 13 August 2021.

[:2-3] 1 2 Janglajew, Klara; Schmeidel, Ewa (2012-11-14). "Periodicity of solutions of nonhomogeneous linear difference equations". Advances in Difference Equations. 2012 (1): 195. doi: 10.1186/1687-1847-2012-195 . ISSN 1687-1847. S2CID 122892501.

[4] Hosch, William L. (1 June 2018). "Rational number". Encyclopedia Britannica. Retrieved 13 August 2021.

[1]

[2]

[3]

[4]