APPLICATION OF LOGIC TO COMBINATORIAL SEQUENCES 5
(i) C-finite or rational if there is a fixed q N\{0} for which a(n) satisfies
for all n q
a(n + q) =
q−1
i=0
pia(n + i)
where each pi Z.
(ii) P-recursive or holonomic if there is a fixed q N\{0} for which a(n)
satisfies for all n q
pq(n) · a(n + q) =
q−1
i=0
pi(n)a(n + i)
where each pi is a polynomial in Z[X] and pq(n) = 0 for any n. We call
it Simply-P-recursive or SP-recursive, if additionally pq(n) = 1 for every
n Z.
(iii) hypergeometric if a(n) satisfies for all n 2
p1(n) · a(n + 1) = p0(n)a(n)
where each pi is a polynomial in Z[X] and p1(n) = 0 for any n. In other
words, a(n) is P-recursive with q = 1.
(iv) MC-finite (modularly C-finite), if for every m N\{0},m 0 there is
q(m) N\{0} for which a(n) satisfies for all n q(m)
a(n + q(m)) =
q(m)−1
i=0
pi(m)a(n + i) mod m
where q(m) and pi(m) depend only on m, and pi(m) Z. Equivalently,
a(n) is MC-finite, if for all m N the sequence a(n) (mod m) is ulti-
mately periodic.
(v) trivially MC-finite, if for each m N and large enough n, f(n) 0
(mod m).
The terminology C-finite and holonomic are due to [83]. P-recursive is due to
[76]. P-recursive sequences were already studied in [12, 13].
The following are well known, see [38, 32].
Lemma 2.1.
(i) Let a(n) be C-finite. Then there is a constant c Z such that a(n) 2cn.
(ii) Furthermore, for every holonomic sequence a(n) there is a constant γ N
such that | a(n) |≤ n!γ for all n 2.
(iii) The sets of C-finite, MC-finite, SP-recursive and P-recursive sequences
are closed under addition, subtraction and point-wise multiplication.
In general, the bound on the growth rate of holonomic sequences is best possi-
ble, since a(n) =
n!m
is easily seen to be holonomic for any integer m, [41].
Proposition 2.2. Let a(n) be a function a : N Z.
(i) If a(n) is C-finite then a(n) is SP-recursive.
(ii) If a(n) is SP-recursive then a(n) is P-recursive.
(iii) If a(n) is SP-recursive then a(n) is MC-finite.
(iv) If a(n) is hypergeometric then a(n) is P-recursive.
5
Previous Page Next Page