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

$$x_n=Ax_{n-1}+Bx_{n-2}$$ (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}$$ (2)

where $\alpha$ and $\beta$ are the Roots of the Quadratic Equation

$$x^2-Ax-B=0,$$ (3)

$$\alpha = {\textstyle{1\over 2}}(A+\sqrt{A^2+4B}\,)$$ (4)

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

The general second-order linear recurrence

$$x_n=Ax_{n-1}+Bx_{n-2}$$ (6)

for constants $A$ and $B$ with arbitrary $x_1$ and $x_2$ has terms

$$x_1 = x_1$$

$$x_2 = x_2$$

$$x_3 = Bx_1+Ax_2$$

$$x_4 = Bx_2+ABx_1+A^2x_2$$

$$x_5 = B^2x_1+2ABx_2+A^2Bx_1+A^3x_2$$

$$x_6 = 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

$$\matrix{ 1\cr 1\cr 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

$$x_n=Ax_{n-1}+Bx_{n-2}+Cx_{n-3}$$ (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

$$Cx^3+Bx^2+Ax=1.$$ (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

$$f_{n+1}=xf_n+yf_{n-1}$$ (12)

can be solved rapidly using a ``rate doubling,''

$$f_{n+2}=(x^2+2y)f_n-y^2f_{n-2},$$ (13)

``rate tripling''

$$f_{n+3}=(x^3+3xy)f_n+y^3f_{n-3},$$ (14)

or in general, ``rate $k$-tupling'' formula

$$f_{n+k}=p_kf_n+q_kf_{n-k},$$ (15)

where

$$p_0 = 2$$ (16)

$$p_1 = x$$ (17)

$$p_k = 2(-y)^{k/2}T_k(x/(2i\sqrt{y}\,))$$ (18)

$$p_{k+1} = xp_k+yp_{k-1}$$ (19)

(here, $T_k(x)$ is a Chebyshev Polynomial of the First Kind) and

$$q_0 = -1$$ (20)

$$q_1 = y$$ (21)

$$q_k = -(-y)^k$$ (22)

$$q_{k+1} = -yq_k$$ (23)

(Beeler et al. 1972, Item 14).

Let

$$s(X)=\prod_{i=1}^m (1-\alpha_iX)^{n_i} = 1-s_1X-\ldots- s_nX^n,$$ (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,$$ (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$$ (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

$$a_{n+3}=2a_{n+2}-4a_{n+1}+4a_n$$ (27)

with

$$a_0=a_1=0$$ (28)

$$a_2=1.$$ (29)

The zeros are

$$a_0=a_1=a_4=a_6=a_{13}=a_{52}=0$$ (30)

(Beukers 1991).

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

References

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.