Manuel Kauers Hagenberg, January 20, 2004 RISC-Linz

Analytic Combinatorics

Homework 12

Exercise 48 Find the bug in the description of the algorithm for computing a Gosper form of a rational function f(x) = s(x)/t(x).

For your convenience, I provide the following verbatim quote of what I actually wrote to the blackboard (according to Laura’s notes, including the bug).

Suppose given f(x) = \frac{s(x)}{t(x)}. Initialize p(x) = 1, q(x) = s(x), r(x + 1) = t(x).

1 Find all critical j ∈ ℕ

Res_{x}(q(x), r(x + j)) = poly(j)

Critical j are positive integer roots of this polynomial

2 If there is no root, done! Otherwise, take the smallest j. Then

d(x) := gcd(q(x), r(x + j))
q(x) = q̄(x)d(x)
r(x + j) = r̄(x + j)d(x)
⟹ \frac{q(x)}{r(x + 1)} = \frac{q̄(x)}{r̄(x + 1)} \frac{d(x)}{d(x − j + 1)}

3 Update:

p(x) := p(x)d(x − j + 1)
q(x) := q̄(x)
r(x + 1) := r̄(x + 1)

4 Goto 1.

This turned out not to give the expected result on the example, because of an index bug in the updating step: d(x − j + 1) should read d(x − j). Sorry about that…

Exercise 49 Show that ∑_{k=0}^{n} \binom{a}{k}k is not Gosper summable.

Apply Gosper’s algorithm. Let f_{k} = \binom{a}{k}k, so

\frac{f_{k+1}}{f_{k}} = \frac{k + 1}{k} \begin{matrix}( & {a \atop k+1} & ) \\ ( & {a \atop k} & ) \end{matrix} = \frac{k + 1}{k} \frac{a(a − 1) … (a − k)k!}{(k + 1)!n(n − 1) … (a − k + 1)} = \frac{a − k}{k} =: f_{rat}(k).

Regarding a as indeterminate, we obtain the Gosper form

f_{rat}(x) = \frac{a − x}{x} = \frac{p(x + 1)}{p(x)} \frac{q(x)}{r(x + 1)}

with p(x) = 1, q(x) = n − x, r(x) = x − 1. Suppose y(x) ∈ ℂ(n)[x] is a solution of the Gosper equation

1 = (a − x)y(x + 1) − (x − 1)y(x).

Assuming deg y = d ≥ 0 we obtain

1 = −2lc(y)x^{d+1} + smaller terms

where lc(y) denotes the leading coefficient of y. Comparing coefficients gives a contradiction, and hence such a y can not exist. The claim follows.