THC Science

In mathematics, a constant-recursive sequence or C-finite sequence is a sequence satisfying a linear recurrence with constant coefficients.

Definition

An order-d homogeneous linear recurrence with constant coefficients is an equation of the form

s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\cdots +c_{d}s(n-d),

where the d coefficients $c_{1},c_{2},\dots ,c_{d}$ are constants.

A sequence $s(0),s(1),s(2),\dots$ is a constant-recursive sequence if there is an order-d homogeneous linear recurrence with constant coefficients that it satisfies for all $n\geq d$ .

Equivalently, $s(n)_{n\geq 0}$ is constant-recursive if the set of sequences

\{s(n+r)_{n\geq 0}:r\geq 0\}

is contained in a vector space whose dimension is finite.

Examples

Fibonacci sequence

The sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... of Fibonacci numbers satisfies the recurrence

F_{n}=F_{n-1}+F_{n-2}

with initial conditions

F_{0}=0

F_{1}=1.

Explicitly, the recurrence yields the values

F_{2}=F_{1}+F_{0}=1

F_{3}=F_{2}+F_{1}=2

F_{4}=F_{3}+F_{2}=3

F_{5}=F_{4}+F_{3}=5

etc.

Lucas sequences

The sequence 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... of Lucas numbers satisfies the same recurrence as the Fibonacci sequence but with initial conditions

L_{0}=2

L_{1}=1.

More generally, every Lucas sequence is a constant-recursive sequence.

Geometric sequences

The geometric sequence $a,ar,ar^{2},\dots$ is constant-recursive, since it satisfies the recurrence $s(n)=rs(n-1)$ for all $n\geq 1$ .

Eventually periodic sequences

A sequence that is eventually periodic with period length $\ell$ is constant-recursive, since it satisfies $s(n)=s(n-\ell )$ for all $n\geq d$ for some d.

Characterization in terms of exponential polynomials

The characteristic polynomial (or "auxiliary polynomial") of the recurrence is the polynomial

x^{d}-c_{1}x^{d-1}-\cdots -c_{d-1}x-c_{d}

whose coefficients are the same as those of the recurrence. The nth term $s(n)$ of a constant-recursive sequence can be written in terms of the roots of its characteristic polynomial. If the d roots $r_{1},r_{2},\dots ,r_{d}$ are all distinct, then the nth term of the sequence is

s(n)=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n}

where the coefficients k_i are constants that can be determined by the initial conditions.

For the Fibonacci sequence, the characteristic polynomial is $x^{2}-x-1$ , whose roots $\phi ={\frac {1+{\sqrt {5}}}{2}}$ and ${\overline {\phi }}={\frac {1-{\sqrt {5}}}{2}}$ appear in Binet's formula

F_{n}={\frac {\phi ^{n}-{\overline {\phi }}^{n}}{\sqrt {5}}}.

More generally, if a root r of the characteristic polynomial has multiplicity m, then the term $r^{n}$ is multiplied by a degree- $(m-1)$ polynomial in n. That is, let $r_{1},\dots ,r_{e}$ be the distinct roots of the characteristic polynomial. Then

s(n)=k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\cdots +k_{e}(n)r_{e}^{n}

where $k_{i}(n)$ is a polynomial of degree $m_{i}-1$ . For instance, if the characteristic polynomial factors as $(x-r)^{3}$ , with the same root r occurring three times, then the nth term is of the form

s(n)=(a+bn+cn^{2})r^{n}.

^[1]

Conversely, if there are polynomials $k_{i}(n)$ such that

s(n)=k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\cdots +k_{e}(n)r_{e}^{n},

then $s(n)_{n\geq 0}$ is constant-recursive.

Characterization in terms of rational generating functions

A sequence is constant-recursive precisely when its generating function

\sum _{n\geq 0}s(n)x^{n}=s(0)+s(1)x^{1}+s(2)x^{2}+s(3)x^{3}+\cdots

is a rational function. The denominator is the polynomial obtained from the auxiliary polynomial by reversing the order of the coefficients, and the numerator is determined by the initial values of the sequence.^[2]

The generating function of the Fibonacci sequence is

{\frac {x}{1-x-x^{2}}}.

In general, multiplying a generating function by the polynomial

1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}

yields a series

\left(s(0)+s(1)x^{1}+s(2)x^{2}+\cdots \right)\left(1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}\right)=\left(b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots \right),

where

b_{n}=s(n)-c_{1}s(n-1)-c_{2}s(n-2)-\cdots -c_{d}s(n-d).

If $s(n)$ satisfies the recurrence relation

s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\cdots +c_{d}s(n-d),

then $b_{n}=0$ for all $n\geq d$ . In other words,

\left(s(0)+s(1)x^{1}+s(2)x^{2}+\cdots \right)\left(1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}\right)=\left(b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots +b_{d-1}x^{d-1}\right),

so we obtain the rational function

\sum _{n\geq 0}s(n)x^{n}={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\cdots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\cdots -c_{d}x^{d}}}.

In the special case of a periodic sequence satisfying $s(n)=s(n-d)$ for $n\geq d$ , the generating function is

{\begin{aligned}{\frac {s(0)+s(1)x^{1}+\cdots +s(d-1)x^{d-1}}{1-x^{d}}}=&\left(s(0)+s(1)x^{1}+\cdots +s(d-1)x^{d-1}\right)+\left(s(0)+s(1)x^{1}+\cdots +s(d-1)x^{d-1}\right)x^{d}+\\&\left(s(0)+s(1)x^{1}+\cdots +s(d-1)x^{d-1}\right)x^{2d}+\cdots \end{aligned}}

by expanding the geometric series.

The generating function of the Catalan numbers is not a rational function, which implies that the Catalan numbers do not satisfy a linear recurrence with constant coefficients.

Non-homogeneous linear recurrence relations with constant coefficients

If the recurrence is non-homogeneous, a particular solution can be found by the method of undetermined coefficients and the solution is the sum of the solution of the homogeneous and the particular solutions. Another method to solve an non-homogeneous recurrence is the method of symbolic differentiation. For example, consider the following recurrence:

a_{n+1}=a_{n}+1

This is an non-homogeneous recurrence. If we substitute n ↦ n+1, we obtain the recurrence

a_{n+2}=a_{n+1}+1

Subtracting the original recurrence from this equation yields

a_{n+2}-a_{n+1}=a_{n+1}-a_{n}

or equivalently

a_{n+2}=2a_{n+1}-a_{n}

This is a homogeneous recurrence, which can be solved by the methods explained above. In general, if a linear recurrence has the form

a_{n+k}=\lambda _{k-1}a_{n+k-1}+\lambda _{k-2}a_{n+k-2}+\cdots +\lambda _{1}a_{n+1}+\lambda _{0}a_{n}+p(n)

where $\lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}$ are constant coefficients and p(n) is the inhomogeneity, then if p(n) is a polynomial with degree r, then this non-homogeneous recurrence can be reduced to a homogeneous recurrence by applying the method of symbolic differencing r times.

If

P(x)=\sum _{n=0}^{\infty }p_{n}x^{n}

is the generating function of the inhomogeneity, the generating function

A(x)=\sum _{n=0}^{\infty }a(n)x^{n}

of the non-homogeneous recurrence

a_{n}=\sum _{i=1}^{s}c_{i}a_{n-i}+p_{n},\quad n\geq n_{r},

with constant coefficients $c i$ is derived from

\left(1-\sum _{i=1}^{s}c_{i}x^{i}\right)A(x)=P(x)+\sum _{n=0}^{n_{r}-1}[a_{n}-p_{n}]x^{n}-\sum _{i=1}^{s}c_{i}x^{i}\sum _{n=0}^{n_{r}-i-1}a_{n}x^{n}.

If P(x) is a rational generating function, A(x) is also one. The case discussed above, where p_n = K is a constant, emerges as one example of this formula, with P(x) = K/(1−x). Another example, the recurrence $a_{n}=10a_{n-1}+n$ with linear inhomogeneity, arises in the definition of the schizophrenic numbers. The solution of homogeneous recurrences is incorporated as p = P = 0.

Notes

^ Greene, Daniel H.; Knuth, Donald E. (1982), "2.1.1 Constant coefficients – A) Homogeneous equations", Mathematics for the Analysis of Algorithms (2nd ed.), Birkhäuser, p. 17.
^ Martino, Ivan; Martino, Luca (2013-11-14). "On the variety of linear recurrences and numerical semigroups". Semigroup Forum. 88 (3): 569–574. doi:10.1007/s00233-013-9551-2. ISSN 0037-1912.

References

Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Welsey. ISBN 0-201-55802-5.

External links

"OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)

[1] Greene, Daniel H.; Knuth, Donald E. (1982), "2.1.1 Constant coefficients – A) Homogeneous equations", Mathematics for the Analysis of Algorithms (2nd ed.), Birkhäuser, p. 17.

[2] Martino, Ivan; Martino, Luca (2013-11-14). "On the variety of linear recurrences and numerical semigroups". Semigroup Forum. 88 (3): 569–574. doi:10.1007/s00233-013-9551-2. ISSN 0037-1912.

[1]

[2]