An Automated Zero Equivalence Test

• Some classes of sequences:

1. f(n + 3) = f(n + 1) − 3f(n): C-finite sequences (trivial)

2. f(n + 2) = (n + 3)f(n + 1) − 3nf(n): P-finite sequences (routine)

3. f(n + 2) = H(n + 3)f(n + 1) − 3^{n}f(n): ΠΣ-sequences (Carsten Schneider)

4. f(n + 2) = H(n + 3)f(n + 1)^{2} − 3^{n}f(n): nonlinear recurrences (MK)

• The larger the class, the less can be done automatically with it.

• Consider the class C, defined by structural induction:

1. Constant sequences belong to C

2. if p is a polynomial in f(n), f(n + 1),…, f(n + r − 1) and f_{i}(n + j) (i = 1, …, s, j = 0, …, r, f_{i} ∈ C), then sequences defined by f(n + r) = p or f(n + r) = 1/p also belong to C.

• Examples:

1. all P-finite sequences

2. Fib(n), 2^{Fib(n)}, Fib(2^{n}) ∈ C (why?)

3. f(n) ∈ C ⟹ ∑_{k=1}^{n} f(k), ∏_{k=1}^{n} f(k) ∈ C

4. continued fractions, orthogonal polynomials, Sylvester sequences, etc.

• We have an algorithm which decides if a given element of C is equivalent to zero. (By A = B ⟺ A − B = 0 this allows to prove identities, note A, B ∈ C ⟹ A − B ∈ C)

• Idea: Use polynomial ideal arithmetic.

1. Consider f(n), f(n + 1), … as variables in a polynomial ring.

2. Consider the polynomial ideal I generated by the recurrences.

3. Decide f(n + r) ∈ I + ⟨f(n), …, f(n + r − 1)⟩ (e.g., by Gröbner basis techniques, see Winkler’s course.) If yes: induction proof, otherwise increase r and try again.

• Example: Prove ∑_{k=1}^{n} k = \frac{1}{2}n^{2} + \frac{1}{2}n

1. Let f_{1}(n) = n, f_{2}(n) = ∑_{k=1}^{n} f_{1}(k), f_{3}(n) = f_{2}(n) − \frac{1}{2}f_{1}(n)^{2} − \frac{1}{2}f_{1}(n).

2. Consider

I = ⟨f_{1}(n + 1) − f_{1}(n) − 1,
f_{2}(n + 1) − f_{2}(n) − f_{1}(n + 1),
f_{3}(n) − f_{2}(n) + \frac{1}{2}f_{1}(n)^{2} + \frac{1}{2}f_{1}(n),
f_{3}(n + 1) − f_{2}(n + 1) + \frac{1}{2}f_{1}(n + 1)^{2} + \frac{1}{2}f_{1}(n + 1)⟩

3. We have f_{3}(n + 1) ∈ I + ⟨f_{3}(n)⟩, therefore the claim holds iff it holds for n = 1.