Manuel Kauers Hagenberg, December 8, 2003 RISC-Linz

Analytic Combinatorics

Homework 9

Exercise 37 Let y(x) ∈ ℂ[[x]]. Prove: y(x) is D-finite if and only if y(x) satisfies a homogenous linear differential equation with polynomial coefficients.

“⇐” Take q = 0.

“⇒” By definition, there exist polynomials q_{0}, …, q_{k} ∈ ℂ[x], not all zero, and q ∈ ℂ such that

q_{k}(x)y^{(k)}(x) + ⋯ + q_{1}(x)y′(x) + q_{0}(x)y(x) = q(x).  (1)

As not all q_{i} are zero, we may assume without loss of generality that q_{k} ≠ 0. (Delete leading zeros if necessary.) If q = 0 then there is nothing to prove. Otherwise, deg q ≥ 0 and D^{1+deg q}q(x) = 0. We apply d := 1 + deg q times the differentiation operator to (1). Using the Leibniz rule in the form

D^{d}(ab) = ∑_{i=0}^{d} \binom{d}{i}(D^{d−i}a)(D^{i}b)

and rearranging terms, we obtain

∑_{i=0}^{d} \binom{d}{i}(q_{k}^{(d−i)}(x)y^{(k+i)}(x) + ⋯ + q_{1}^{(d−i)}(x)y^{(1+i)}(x) + q_{0}^{(d−i)}(x)y^{(i)}(x)) = 0.

Clearly this is a homogenous linear differential equation with polynomial coefficients. It remains to show that at least one of the coefficients is not zero. Indeed, it is easily seen that the coefficient of y^{(d+k)}(x) is q_{k}(x) which was assumed not to be zero.

Exercise 38 Prove: A sequence (f_{n})_{n=0}^{∞} is P-finite if and only if its generating

function f(x) = ∑_{n=0}^{∞} f_{n}x^{n} is D-finite.

“⇒” Let (f_{n}) satisfy the recurrence

p_{r}(n)f_{n+r} + ⋯ + p_{1}(n)f_{n+1} + p_{0}(n)f_{n} = 0.

Consider the corresponding generating functions equation,

∑_{n=0}^{∞} p_{r}(n)f_{n+r}x^{n} + ⋯ + ∑_{n=0}^{∞} p_{0}(n)f_{n}x^{n} = 0.  (2)

We have to show that the left hand side is an affine linear combination of f(x) and its derivatives with polynomial coefficients. It suffices to show this for the ith term in this representation, i = 0, …, r. Let p_{i}(n) = a_{d}n\underline{d} + a_{d−1}n\underline{d−1} + ⋯ + a_{0} be the representation of p_{i} in the falling factorial basis, i.e.,

∑_{n=0}^{∞} p_{i}(n)f_{n+i}x^{n} = a_{d} ∑_{n=0}^{∞} n\underline{d}f_{n+i}x^{n} + ⋯ + a_{0} ∑_{n=0}^{∞} f_{n+i}x^{n}.  (3)

In order to show that this is an affine linear combination of f(x), f′(x), … with polynomial coefficients, it is again sufficient to consider one of the terms, e.g., the jth. We observe

∑_{n=0}^{∞} n\underline{j}f_{n+i}x^{n} = ∑_{n=j}^{∞} n\underline{j}f_{n+i}x^{n} = x^{j} ∑_{n=j}^{∞} n\underline{j}f_{n+i}x^{n−j} = x^{j} \frac{∂^{j}}{∂^{j}x} ∑_{n=j}^{∞} f_{n+i}x^{n}  (4)

=^{(∗)} x^{j} \frac{∂^{j}}{∂^{j}x} ∑_{n=0}^{∞} f_{n+i}x^{n} = x^{j} \frac{∂^{j}}{∂^{j}x} \frac{1}{x^{i}} ∑_{n=i}^{∞} f_{n}x^{n} = x^{j} \frac{∂^{j}}{∂^{j}x}(\frac{1}{x^{i}} (f(x) + poly))

where the “poly” accounts for the index transform. Note in (∗) that the correction polynomial required for the index transform is of degree less than j and hence killed by the j-fold derivation. We succeeded in writing the left hand side of (4) (and hence also the one of (3), and hence also the one of (2) ) as affine linear combination of f(x), f′(x), …, f^{(r)}(x) with rational coefficients. Clearing denominators completes the proof.

“⇐” By definition we have

q_{r}(x)f^{(r)}(x) + ⋯ + q_{1}(x)f′(x) + q_{0}(x)f(x) = 0

for certain q_{i} ∈ ℂ[x], hence

q_{r}(x) ∑_{n=r}^{∞} n\underline{r}f_{n}x^{n−r} + ⋯ + q_{0}(x) ∑_{n=0}^{∞} f_{n}x^{n} = 0

Expanding the polynomials and comparing coefficients already proves the claim.

Remark: We have actually proven more: (f_{n})_{n=0}^{∞} is holonomic with a recurrence of order r if and only if f(x) is holonomic with a differential equation of order r. Together with knowledge from analysis, this could be used for an alternative solution of Exercise 9 on Sheet 3.

Exercise 39 Let f_{n} be the number of ways from (0, 0) to (n, n) in ℤ×ℤ consisting of steps (1, 0), (0, 1), (1, 1). Prove:

a) (f_{n})_{n=0}^{∞} satisfies the recurrence

(n + 2)f_{n+2} − 3(2n + 3)f_{n+1} + (n + 1)f_{n} = 0.

b) The generating function f(x) of (f_{n})_{n=0}^{∞} has the closed form

f(x) = \frac{1}{\sqrt{x^{2} − 6x + 1}}.

Ad a) We apologize in advance for the following brute force proof. Consider the number h_{n,m} of ways from (0, 0) to (n, m) using only the admissible steps. Note that f_{n} = h_{n,n} and that

h_{n,m} = h_{n−1,m−1} + h_{n−1,m} + h_{n,m−1}  (m, n > 0)
h_{0,m} = h_{n,0} = 1  (m, n ∈ ℕ_{0})

Consider the univariate generating function H_{n}(y) of h_{n,m}. For n > 0, we have

H_{n}(y) := ∑_{m=0}^{∞} h_{n,m}y^{m} = 1 + ∑_{m=1}^{∞} h_{n,m}y^{m}

= 1 + ∑_{m=1}^{∞} h_{n−1,m−1}y^{m} + ∑_{m=1}^{∞} h_{n−1,m}y^{m} + ∑_{m=1}^{∞} h_{n,m−1}y^{m}

= 1 + yH_{n−1}(y) + (H_{n−1}(y) − 1) + yH_{n}(y)

(1 − y)H_{n}(y) = (1 + y)H_{n−1}(y).

In addition, we have H_{0}(y) = \frac{1}{1−y} because h_{0,m} = 1 for all m. This gives

H_{n}(y) = \frac{1}{1 − y} (\frac{1 + y}{1 − y} )^{n} (n ≥ 0).

By construction, we have

f_{n} = h_{n,n} = ⟨y^{n}⟩H_{n}(y) = ⟨y^{n}⟩(1 + y)^{n} \frac{1}{(1 − y)^{n+1}}

= ⟨y^{n}⟩ ∑_{m=0}^{∞} \binom{n}{m}y^{m} · ∑_{m=0}^{∞} \binom{n + m}{m}y^{m}

= ⟨y^{n}⟩ ∑_{m=0}^{∞} ∑_{k=0}^{m} \binom{n}{m − k}\binom{n + k}{k}y^{m}

= ∑_{k=0}^{n} \binom{n}{n − k}\binom{n + k}{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n + k}{k}.

Probably this sum also has some nice combinatorial interpretation. Anyway, the sum is hypergeometric, and Zeilberger quickly finds the desired recurrence for f_{n}.

Ad b) Starting from the recurrence, we get

(n + 2)f_{n+2} − 3(2n + 3)f_{n+1} + (n + 1)f_{n} = 0
∑_{n=0}^{∞}(n + 2)f_{n+2}x^{n} − 3 ∑_{n=0}^{∞}(2n + 3)f_{n+1}x^{n} + ∑_{n=0}^{∞}(n + 1)f_{n}x^{n} = 0

∑_{n=1}^{∞} n(f_{n+2} − 6f_{n+1} + f_{n})x^{n} + ∑_{n=0}^{∞}(2f_{n+2} − 9f_{n+1} + f_{n})x^{n} = 0

x\frac{∂}{∂x} ∑_{n=0}^{∞}(f_{n+2} − 6f_{n+1} + f_{n})x^{n} + ∑_{n=0}^{∞}(2f_{n+2} − 9f_{n+1} + f_{n})x^{n} = 0

x\frac{∂}{∂x}(\frac{f(x) − 3x − 1}{x^{2}} − 6\frac{f(x) − x}{x} + f(x))

+ (2\frac{f(x) − 3x − 1}{x^{2}} − 9\frac{f(x) − x}{x} + f(x)) = 0
(x^{2} − 6x + 1)f′(x) + (x − 3)f(x) = 0

Two further steps lead to the solution

f(x) = α\frac{1}{\sqrt{x^{2} − 6x + 1}}

of the differential equation. f(0) = f_{0} = 1 gives α = 1, and we are done.

Exercise 40 Prove that e^{x} is not an algebraic power series. Assume otherwise. Then there exists polynomials Q_{0}, … Q_{k} ∈ ℂ[x], Q_{k} ≠ 0 such that

Q_{k}(x)e^{kx} + ⋯ + Q_{1}(x)e^{x} + Q_{0}(x) = 0  | · e^{−kx}
Q_{k}(x) + Q_{k−1}(x)e^{−x} + ⋯ + Q_{0}(x)e^{−kx} = 0  | : x^{deg Q_{k}}
\frac{Q_{k}(x)}{x^{deg Q_{k}}} + \frac{Q_{k−1}(x)}{x^{deg Q_{k}}}e^{−x} + ⋯ + \frac{Q_{0}(x)}{x^{deg Q_{k}}} e^{−kx} = 0  | x → ∞
Lc(Q_{k}) = 0,

where Lc(Q_{k}) ≠ 0 is the leading coefficient of Q_{k}. Contradiction.