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

(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