Linear Recurrent Sequences

This text is the result of [1], which has been written for a very nice subject called “Seminario Elemental de Álgebra” (something like Elementary course of Algebra), and it was written after the study of [1] and during the specification and implementation in Smalltalk (an objects ambient,living together in a computer) of the linear recurrent sequences.

1. Some definitions

Some of the following definitions were taken from [1].

Definition. A sequence {x_{n}}_{n∈IN} ∈ C^{IN} is said to be linear recurrent of order less or equal than k if there exists k complex numbers α_{0}, α_{1}, …, α_{k−1} such that

x_{n+k} = α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + a_{k−1}.x_{n+k−1} ∀n ∈ IN  (1)

Definition. Given a linear recurrent sequence {x_{n}}_{n∈IN} ∈ C^{IN}, we define the order of {x_{n}}_{n∈IN} (and noted ord({x_{n}}_{n∈IN})) to the positive integer:

i) 1 if {x_{n}}_{n∈IN} is a linear recurrent sequence of order less or equal than 1, (e.g. if {x_{n}}_{n∈IN} is a geometric progression).

ii) k if {x_{n}}_{n∈IN} is a linear recurrent sequence of order less or equal than k but is not a liner recurrent sequence of order less or equal than (k − 1).

Definition. If p = ∑_{i=0}^{k} α_{i}x^{i} ∈ C[X] − {0} is a polynomial of degree k and {x_{n}}_{n∈IN} a linear recurrent sequence. We say that {x_{n}}_{n∈IN} satisfies p if

α_{0}.x_{n} + α_{1}.x_{n+1} + ⋯ + a_{k−1}.x_{n+k−1} = 0 ∀n ∈ IN

Definition. We denote f = X_{a_{n}}, f ∈ C[X], and we say that f is the characteristic polynomial of {a_{n}}_{n∈IN}, if f is monic, ord({a_{n}}_{n∈IN}) = deg (f) and f({a_{n}}) = 0.

There exists a matrix representation of (1) and the characteristic polynomial of that matrix is the same as the minimal one, and the same as of the last definition. (for further details guess... yes! [1]).

Linear Recurrent Sequences Eric Rodríguez Guevara

2. Structure of the linear recurrent sequences

In [1] it’s proved that S_{p} = {{x_{n}}_{n∈IN} ∈ C^{IN}/{x_{n}}_{n∈IN} is a linear recurrent sequence that satisfies p}

is a C vector subspace of C^{IN} of dimention deg (p). And that the set S ⊂ C^{IN} of all linear recurrent sequences is a C vector subspace. In the proof they use a lemma which says that if {x_{n}}_{n∈IN} satisfies p, then for all polynomial q, {x_{n}}_{n∈IN} also satisfies q · p. 2.1 Properties of evaluating the sequences at polynomials.

Let f = ∑_{i=0}^{k} α_{i}x^{i} and g = ∑_{i=0}^{l} β_{i}x^{i} be two polynomials, where f = X_{a_{n}}, g = X_{b_{n}}, {a_{n}}_{n∈IN} and {b_{n}}_{n∈IN} are not null sequences.

1. If f = p · q and p, q ∉ C , then p({a_{n}}) ≠ 0 and q({b_{n}}) ≠ 0 since f is the minimal that is zero at a_{n}.

2. (f + g)\{c_{n}\} = 0 ⇏ f(\{c_{n}\}) = 0 and g(\{c_{n}\}) = 0. A counterexample is \overline{f} = f − α_{0}, where it’s clear that α_{o}(\{a_{n}\}) ≠ 0 and \overline{f}(\{a_{n}\}) ≠ 0 because f is minimal.

3. If (f + g)({c_{n}}) = 0 and f({c_{n}}) = 0, then g({c_{n}}) = 0, filling with zeros if it’s needed we have

(f + g) = ∑_{i=0}^{k} (α_{i} + β_{i})x^{i}
(f + g)({c_{n}}) = ∑_{i=0}^{k}(α_{i} + β_{i})c_{n+i}

= ∑_{i=0}^{k} α_{i}c_{n+i} + ∑_{i=0}^{k} β_{i}c_{n+i}

= ∑_{i=0}^{k} β_{i}c_{n+i}

= g({c_{n}})

Linear Recurrent Sequences Eric Rodríguez Guevara 4. The set I_{a_{n}} = {p ∈ C[X]/p({a_{n}}) = 0} is the same as fC[X] for if p({a_{n}}) = 0 then

p = f · q + r
p({a_{n}}) = (f · q + r)({a_{n}})
= r({a_{n}})

hence r = 0 or deg (r) < deg (f), so we have r = 0 because of the definition of f. Corollary. [f; g]({a_{n} + b_{n}}) = 0.

This is evident hence [f; g] is a multiple of f and of g so evaluated at a_{n} and b_{n} it’s zero, but being S_{[f;g]} a linear subspace, we conclude that [f; g]({a_{n} + b_{n}}) = 0. Corollary. Let m = X_{a_{n}+b_{n}} and

\overline{f} = \frac{f}{(f; g)} y \overline{g} = \frac{g}{(f; g)}

then

máx\{deg (\overline{f} · \overline{g}), 1\} ≤ deg (m) ≤ deg ([f; g])

Hence m({a_{n} + b_{n}}) = 0 and f({a_{n}}) = 0 we have that (m · f)({a_{n} + b_{n}}) = 0 and (m · f)({a_{n}}) = 0, because S_{m·f} is a linear subspace, {b_{n}} ∈ S_{m·f} , so g/f · m since g generates I_{b_{n}}, cancelling f and g common roots, we have that \overline{g}/ \overline{f} · m, so \overline{g}/m. Same way we have \overline{f}/m. Being \overline{f} ⊥ \overline{g} we have the proof.

Bibliography.

[1] Juan Sabia, Susana Tesauri, Sucesiones Recursivas Lineales, Notas de Matemática, 5 (U.B.A 1997).