Metraipolis › archive › dc_6cc6ecf029fd

Constant-recursive sequence — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Constant-recursive_sequence
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T16:30:35.430Z
SHA-256 of the archived text
0a1a5c8c4680774a70c8eeacdcc1ac75ee4d42b3b0b1dfad16db680bce3ca76d
Stable URL of this page
https://metraipolis.com/documento/dc_6cc6ecf029fd

How to cite

Constant-recursive sequence — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Constant-recursive_sequence (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_6cc6ecf029fd (Metraipolis archive dc_6cc6ecf029fd, sha256 0a1a5c8c4680774a70c8eeacdcc1ac75ee4d42b3b0b1dfad16db680bce3ca76d)
BibTeX
@misc{dc6cc6ecf029fd,
  title = {Constant-recursive sequence — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Constant-recursive_sequence},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_6cc6ecf029fd; sha256 0a1a5c8c4680774a70c8eeacdcc1ac75ee4d42b3b0b1dfad16db680bce3ca76d},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Constant-recursive_sequence. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In mathematics, an infinite sequence of numbers s 0 , s 1 , s 2 , s 3 , … {\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots } is called constant-recursive if it satisfies an equation of the form s n = c 1 s n − 1 + c 2 s n − 2 + ⋯ + c d s n − d , {\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},} for all n ≥ d {\displaystyle n\geq d} , where c i {\displaystyle c_{i}} are constants. The equation is called a linear recurrence relation. The concept is also known as a linear recurrence sequence, linear-recursive sequence, linear-recurrent sequence, or a C-finite sequence. For example, the Fibonacci sequence 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , … {\displaystyle 0,1,1,2,3,5,8,13,\ldots } , is constant-recursive because it satisfies the linear recurrence F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} : each number in the sequence is the sum of the previous two. Other examples include the power of two sequence 1 , 2 , 4 , 8 , 16 , … {\displaystyle 1,2,4,8,16,\ldots } , where each number is the sum of twice the previous number, and the square number sequence 0 , 1 , 4 , 9 , 16 , 25 , … {\displaystyle 0,1,4,9,16,25,\ldots } . All arithmetic progressions, all geometric progressions, and all polynomials are constant-recursive. However, not all sequences are constant-recursive; for example, the factorial sequence 1 , 1 , 2 , 6 , 24 , 120 , … {\displaystyle 1,1,2,6,24,120,\ldots } is not constant-recursive. Constant-recursive sequences are studied in combinatorics and the theory of finite differences. They also arise in algebraic number theory, due to the relation of the sequence to polynomial roots; in the analysis of algorithms, as the running time of simple recursive functions; and in the theory of formal languages, where they count strings up to a given length in a regular language. Constant-recursive sequences are closed under important mathematical operations such as term-wise addition, term-wise multiplication, and Cauchy product. The Skolem–Mahler–Lech theorem states that the zeros of a constant-recursive sequence have a regularly repeating (eventually periodic) form. The Skolem problem, which asks for an algorithm to determine whether a linear recurrence has at least one zero, is an unsolved problem in mathematics.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Linear algebra»).
Fonte: Wikipedia in inglese, voce «Constant-recursive sequence» — https://en.wikipedia.org/wiki/Constant-recursive_sequence
Wikidata Q23835453 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q23835453
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Constant-recursive_sequence?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1378614853, consultata il 2026-10-06T15:17:32.743Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 49127554a5c055c4c265c5ee5989b9baf5254ac1e9bd8100a2c47cf1fd4d46c0