Manuel Kauers Hagenberg, January 10, 2004 RISC-Linz

Analytic Combinatorics

Homework 11

Exercise 44 Prove: If the Gosper equation does not have a polynomial solution, then the telescoping equation does not have a hypergeometric solution.

See GKP, page 255f; or A = B, page 75ff.

Exercise 45 In the notation of the lecture, prove that g_{k+1}/g_{k} = g_{rat}(k) in Gosper’s algorithm.

Let f_{k}, p, q, r, g_{rat} be as in the lecture. Then

\frac{g_{k+1}}{g_{k}} = \frac{f_{k+1}}{f_{k}} · \frac{g_{rat}(k) − 1}{g_{rat}(k + 1) − 1}

= \frac{p(k + 1)}{p(k)} · \frac{q(k)}{r(k + 1)} · \frac{\frac{y(k+1)}{y(k)} · \frac{q(k)}{r(k)} − 1}{\frac{y(k+2)}{y(k+1)} · \frac{q(k+1)}{r(k+1)} − 1}

= \frac{p(k + 1)}{p(k)} · \frac{q(k)}{r(k + 1)} · \frac{\frac{y(k+1)q(k)−y(k)r(k)}{y(k)r(k)}}{\frac{y(k+2)q(k+1)−y(k+1)r(k+1)}{y(k+1)r(k+1)}}

= \frac{p(k + 1)}{p(k)} · \frac{q(k)}{r(k + 1)} · \frac{p(k)y(k + 1)r(k + 1)}{p(k + 1)y(k)r(k)}

= \frac{y(k + 1)q(k)}{y(k)r(k)} = g_{rat}(k).

Exercise 46 Use Gosper’s Algorithm to evaluate the following sums:

a) ∑_{k=0}^{n} q^{k} (q ∈ ℂ fixed)

b) ∑_{k=0}^{n}(−1)^{k}\binom{a}{k} (a ∈ ℂ fixed)

c) ∑_{k=1}^{n}(−1)^{k} \frac{k}{4k^{2} − 1}_{d) ∑_{k=1}^{n} \frac{1}{4k^{2} − 1}}

Ad a) Let f_{k} = q^{k}. Then \frac{f_{k+1}}{f_{k}} = q and we may take

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

with p(x) = 1, q(x) = q, r(x) = 1. The Gosper equation

1 = q y(x + 1) − r(x)y(x)

has the solution y(x) = \frac{1}{q−1}. Hence we have

g_{rat}(x) = \frac{\frac{1}{q−1}q}{\frac{1}{q−1}1} = q

and therefore

g_{k} = \frac{1}{q − 1}q^{k}.

It follows that

∑_{k=0}^{n} q^{k} = g_{n+1} − g_{0} = \frac{q^{n+1} − 1}{q − 1},

as it should. Ad b) Let f_{k} = (−1)^{k}\binom{a}{k}. Then \frac{f_{k+1}}{f_{k}} = \frac{k−a}{k+1} and we may take

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

with p(x) = 1, q(x) = x−a and r(x) = x, assuming that a is not a negative integer. The Gosper equation

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

has the solution y(x) = −1/a. Hence we have

g_{rat}(x) = \frac{−\frac{1}{a}(x − a)}{−\frac{1}{a}x} = \frac{x − a}{x}

and therefore

g_{k} = \frac{1}{\frac{k−a}{k} − 1}(−1)^{k}\binom{a}{k} = \frac{k}{a} (−1)^{k+1}\binom{a}{k}.

It follows that

∑_{k=0}^{n}(−1)^{k}\binom{a}{k} = g_{n+1} − g_{0} = \frac{n + 1}{a}(−1)^{n}\binom{a}{n + 1} = (−1)^{n}\binom{a − 1}{n}.

Ad c) Let f_{k} = (−1)^{k} \frac{k}{4k^{2}−1}. Then \frac{f_{k+1}}{f_{k}} = −\frac{k+1}{k} \frac{2k−1}{2k+3} and we may take

f_{rat}(x) = \frac{x + 1}{x} \frac{1 − 2x}{2x + 3}

with p(x) = x, q(x) = 1 − 2x, r(x) = 2x + 1. The Gosper equation

x = (1 − 2x)y(x + 1) − (2x + 1)y(x)

has the solution y(x) = −1/4. Hence we have

g_{rat}(x) = \frac{−\frac{1}{4}(1 − 2x)}{−\frac{1}{4}(2x + 1)} = \frac{1 − 2x}{2x + 1}

and therefore

g_{k} = \frac{1}{\frac{1−2k}{2k+1} − 1}(−1)^{k} \frac{k}{4k^{2} − 1} = \frac{1}{4}(−1)^{k−1} \frac{1}{2k − 1}.

It follows that

∑_{k=1}^{n}(−1)^{k} \frac{k}{4k^{2} − 1} = g_{n+1} − g_{1} = \frac{1}{4}((−1)^{n} \frac{1}{2n + 1} − 1).

Ad d) Let f_{k} = \frac{1}{4k^{2}−1}. then \frac{f_{k+1}}{f_{k}} = \frac{k+1}{k} \frac{2k−1}{2k+3} and we may take

f_{rat}(x) = \frac{x + 1}{x} \frac{2x − 1}{2x + 3}

with p(x) = x, q(x) = 2x − 1, r(x) = 2x + 1. The Gosper equation

x = (2x − 1)y(x + 1) − (2x + 1)y(x)

now has the solution y(x) = −\frac{1}{2}x+β for arbitrary β. We are lazy and choosse β = 0. Then we have

g_{rat}(x) = \frac{−\frac{1}{2}(x + 1)}{−\frac{1}{2}x} \frac{2x − 1}{2x + 1} = \frac{(x + 1)(2x − 1)}{x(2x + 1)}

and therefore

g_{k} = \frac{1}{\frac{(k+1)(2k−1)}{k(2k+1)} − 1} \frac{1}{4k^{2} − 1} = \frac{k}{1 − 2k}

It follows that

∑_{k=1}^{n}(−1)^{k} \frac{1}{4k^{2} − 1} = g_{n+1} − g_{1} = 1 − \frac{n + 1}{2n + 1}.

Cool.

Exercise 47 Use Gosper’s Algorithm to prove that the sequence H_{n} of harmonic

numbers (H_{n} = ∑_{k=1}^{n} 1/k) is not hypergeometric (and hence, in particular, not ratio-

nal)

We try to evaluate ∑_{k=1}^{n} \frac{1}{k}. Writing f_{k} = 1/k we have \frac{f_{k+1}}{f_{k}} = \frac{k}{k+1}, so we may put

put

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

with p(x) = 1, q(x) = x, r(x) = x. The Gosper equation

1 = xy(x + 1) − xy(x)

can not have a polynomial solution, because pluging such a solution into the right hand side would necessarily yield a polynomial with constant term 0 ≠ 1 on the right hand side. That’s it.