info prev up next book cdrom email home

Recurrence Sequence

A sequence of numbers generated by a Recurrence Relation is called a recurrence sequence. Perhaps the most famous recurrence sequence is the Fibonacci Numbers.

If a sequence $\{x_n\}$ with $x_1=x_2=1$ is described by a two-term linear recurrence relation of the form

\end{displaymath} (1)

for $n\geq 3$ and $A$ and $B$ constants, then the closed form for $x_n$ is given by
x_n={\alpha^n-\beta^n\over \alpha-\beta}
\end{displaymath} (2)

where $\alpha$ and $\beta$ are the Roots of the Quadratic Equation
\end{displaymath} (3)

$\displaystyle \alpha$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}(A+\sqrt{A^2+4B}\,)$ (4)
$\displaystyle \beta$ $\textstyle =$ $\displaystyle {\textstyle{1\over 2}}(A-\sqrt{A^2+4B}\,).$ (5)

The general second-order linear recurrence

\end{displaymath} (6)

for constants $A$ and $B$ with arbitrary $x_1$ and $x_2$ has terms
$\displaystyle x_1$ $\textstyle =$ $\displaystyle x_1$  
$\displaystyle x_2$ $\textstyle =$ $\displaystyle x_2$  
$\displaystyle x_3$ $\textstyle =$ $\displaystyle Bx_1+Ax_2$  
$\displaystyle x_4$ $\textstyle =$ $\displaystyle Bx_2+ABx_1+A^2x_2$  
$\displaystyle x_5$ $\textstyle =$ $\displaystyle B^2x_1+2ABx_2+A^2Bx_1+A^3x_2$  
$\displaystyle x_6$ $\textstyle =$ $\displaystyle B^2x_2+2AB^2x_1+3A^2Bx_2+A^3Bx_1+A^4x_2.$  

Dropping $x_1$, $x_2$, and $A$, this can be written

B & 1\cr
B & B & 1\cr
B^2 & 2B & B & 1\cr
B^2 & 2B^2 & 3B & B & 1,\cr}

which is simply Pascal's Triangle on its side. An arbitrary term can therefore be written as

$x_n=\sum_{k=0}^{n-2}{\left\lfloor{{\textstyle{1\over 2}}(n+k-2)}\right\rfloor \...
...)/2}\right\rfloor } {x_1}^{[n+k{\rm\ (mod\ }2)]}{x_2}^{[n+k+1{\rm\ (mod\ }2)]}.$ (7)
$= -(Ax_1-x_2)\sum_{k=0}^{n-2} A^{2k-n+2}B^{-k+n-2}{k\choose n-k-2}$
$ +x_1 \sum_{k=0}^{n-1} A^{2k-n+1}B^{-k+n-1}{k\choose n-k-1}.\quad$ (8)

The general linear third-order recurrence

\end{displaymath} (9)

has solution

$x_n=x_1\left({{\alpha^{-n}\over A+2\alpha B+3\alpha^2 C}+{\beta^{-n}\over A+2\beta B+3\beta^2 C}+{\gamma^{-n}\over A+2\gamma B+3\gamma^2 C}}\right)$
$-(Ax_1-x_2)\left({{\alpha^{1-n}\over A+2\alpha B+3\alpha^2 C}+{\beta^{1-n}\over A+2\beta B+3\beta^2 B}+{\gamma^{1-n}\over A+2\gamma C+3\gamma^2 C}}\right)$
$-(Bx_1+Ax_2-x_3)\left({{\alpha^{2-n}\over A+2\alpha B+3\alpha^2 C}+{\beta^{2-n}\over A+2\beta B+3\beta^2 C}+{\gamma^{2-n}\over A+2\gamma B+3\gamma^2 C}}\right),$ (10)
where $\alpha$, $\beta$, and $\gamma$ are the roots of the polynomial

\end{displaymath} (11)

A Quotient-Difference Table eventually yields a line of 0s Iff the starting sequence is defined by a linear recurrence relation.

A linear second-order recurrence

\end{displaymath} (12)

can be solved rapidly using a ``rate doubling,''
\end{displaymath} (13)

``rate tripling''
\end{displaymath} (14)

or in general, ``rate $k$-tupling'' formula
\end{displaymath} (15)

$\displaystyle p_0$ $\textstyle =$ $\displaystyle 2$ (16)
$\displaystyle p_1$ $\textstyle =$ $\displaystyle x$ (17)
$\displaystyle p_k$ $\textstyle =$ $\displaystyle 2(-y)^{k/2}T_k(x/(2i\sqrt{y}\,))$ (18)
$\displaystyle p_{k+1}$ $\textstyle =$ $\displaystyle xp_k+yp_{k-1}$ (19)

(here, $T_k(x)$ is a Chebyshev Polynomial of the First Kind) and
$\displaystyle q_0$ $\textstyle =$ $\displaystyle -1$ (20)
$\displaystyle q_1$ $\textstyle =$ $\displaystyle y$ (21)
$\displaystyle q_k$ $\textstyle =$ $\displaystyle -(-y)^k$ (22)
$\displaystyle q_{k+1}$ $\textstyle =$ $\displaystyle -yq_k$ (23)

(Beeler et al. 1972, Item 14).


s(X)=\prod_{i=1}^m (1-\alpha_iX)^{n_i} = 1-s_1X-\ldots- s_nX^n,
\end{displaymath} (24)

where the generalized Power sum $a(h)$ for $h=0$, 1, ... is given by
a(h)=\sum_{i=1}^m A_i(h){\alpha_i}^h,
\end{displaymath} (25)

with distinct Nonzero roots $\alpha_i$, Coefficients $A_i(h)$ which are Polynomials of degree $n_i-1$ for Positive Integers $n_i$, and $i\in[1,m]$. Then the sequence $\{a_h\}$ with $a_h=a(h)$ satisfies the Recurrence Relation
a_{h+n}=s_i a_{h+n-1}+\ldots+s_n a_h
\end{displaymath} (26)

(Meyerson and van der Poorten 1995).

The terms in a general recurrence sequence belong to a finitely generated Ring over the Integers, so it is impossible for every Rational Number to occur in any finitely generated recurrence sequence. If a recurrence sequence vanishes infinitely often, then it vanishes on an arithmetic progression with a common difference 1 that depends only on the roots. The number of values that a recurrence sequence can take on infinitely often is bounded by some Integer $l$ that depends only on the roots. There is no recurrence sequence in which each Integer occurs infinitely often, or in which every Gaussian Integer occurs (Myerson and van der Poorten 1995).

Let $\mu(n)$ be a bound so that a nondegenerate Integer recurrence sequence of order $n$ takes the value zero at least $\mu(n)$ times. Then $\mu(2)=1$, $\mu(3)=6$, and $\mu(4)\geq 9$ (Myerson and van der Poorten 1995). The maximal case for $\mu(3)$ is

\end{displaymath} (27)

\end{displaymath} (28)

\end{displaymath} (29)

The zeros are
\end{displaymath} (30)

(Beukers 1991).

See also Binet Forms, Binet's Formula, Fast Fibonacci Transform, Fibonacci Sequence, Lucas Sequence, Quotient-Difference Table, Skolem-Mahler-Lerch Theorem


Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, Feb. 1972.

Beukers, F. ``The Zero-Multiplicity of Ternary Recurrences.'' Composito Math. 77, 165-177, 1991.

Myerson, G. and van der Poorten, A. J. ``Some Problems Concerning Recurrence Sequences.'' Amer. Math. Monthly 102, 698-705, 1995.

info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein