Manuel Kauers Hagenberg, January 27, 2004 RISC-Linz

Analytic Combinatorics

Homework 13

Exercise 50 Use Sister Celine’s Algorithm to evaluate the sum f(n) = ∑_{k=0}^{n} \binom{n}{k}x^{k}.

Write F (n, k) = \binom{n}{k}x^{k}.

a_{00}F (n, k) + a_{10}F (n + 1, k) + a_{01}F (n, k + 1) + a_{11}F (n + 1, k + 1) = 0
a_{00} + a_{10} \frac{n + 1}{n + 1 − k} + a_{01} \frac{n − k}{k + 1} + a_{11} \frac{n + 1}{k + 1} = 0
(a_{01}x − a_{00})k^{2} +
+ (a_{10}n + a_{10} − a_{01}x + a_{00}n − 2a_{01}xn − a_{11}xn − a_{11}x)k +
+ (a_{11}xn^{2} + a_{00}n + a_{00} + a_{11}x + a_{01}xn^{2} + a_{01}xn + a_{10} + 2a_{11}xn) = 0

We arrive at the following linear system for the a_{ij}.

(\begin{matrix}−1 & x & 0 & 0 \\ n & −x(1 + 2n) & n + 1 & −x(n + 1) \\ n + 1 & xn(n + 1) & n + 1 & x(n + 1)^{2} \end{matrix}) (\begin{matrix}a_{00} \\ a_{01} \\ a_{01} \\ a_{11} \end{matrix}) = 0

The solution space is given by

(a_{00}, a_{01}, a_{10}, a_{11}) = (−tx, 0, −t, t)

with t as parameter. Choosing t = −1 we obtain the recurrence

xF (n, k) + F (n, k + 1) − F (n + 1, k + 1) = 0
xf(n) + f(n) − f(n + 1) = 0
f(n + 1) = (x + 1)f(n).

Together with f(0) = 1 we obtain the desired result f(n) = (1 + x)^{n}.

Exercise 51 Use Zeilberger’s Algorithm to evaluate the sum ∑_{k=0}^{n} k\binom{n}{k}.

Write F (n, k) = k\binom{n}{k}. We are optimistic and try first order 0.

f_{k} := F (n, k) = k\binom{n}{k}. We have \frac{f_{k+1}}{f_{k}} = \frac{n−k}{k}, and therefore

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

where we may take p(x) = 1, q(x) = n − x, r(x) = x − 1. It is easily seen that the Gosper equation

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

does not have a polynomial solution y(x) (compare coefficients). We have been too optimistic. Next, we try order 1. f_{k} := a_{0}F (n, k) + a_{1}F (n + 1, k). Now we have

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

and we may take p(x) = a_{0}(n + 1 − x) + a_{1}(n + 1), q(x) = n + 1 − x, r(x) = x − 1. The Gosper equation thus reads

a_{0}(n + 1 − x) + a_{1}(n + 1) = (n + 1 − x)y(x + 1) − (x − 1)y(x)

Hoping for a solution y(x) = y_{0} of degree 0 and rearranging terms we are lead to

−a_{0}x + (a_{0} + a_{1})(n + 1) = −2xy_{0} + (n + 2)y_{0}

which has y_{0} = 1, a_{0} = 2, a_{1} = −\frac{n}{n+1}, for example, as an obvious solution. Proceeding in the course of Gosper’s algorithm, we have

g_{rat}(x) = \frac{y(x + 1)}{y(x)} \frac{q(x)}{r(x)} = \frac{n + 1 − x}{x − 1}
g_{k} = \frac{1}{g_{rat}(k) − 1}f_{k} = \frac{k − 1}{n + 1 − k} F (n, k).

This gives the certificate R(n, k) = \frac{k−1}{n+1−k} and the recurrence

2F (n, k) − \frac{n}{n + 1}F (n + 1, k) = g_{k+1} − g_{k}
2f(n) = \frac{n}{n + 1}f(n + 1)
f(n + 1) = 2\frac{n + 1}{n}f(n).

Together with f(1) = 1 this confirms the result f(n) = n2^{n−1} from the lecture.

Q. E. D. — Quite Enough Done.