Manuel Kauers Hagenberg, December 1, 2003 RISC-Linz

Analytic Combinatorics

Homework 8

Exercise 33 Let (F_{k}(x))_{k≥0} be a sequence in ℂ[[x]]. Prove: The following three statements are equivalent.

(i) lim_{k→∞} ord F_{k}(x) = ∞

(ii) ∑_{k=0}^{∞} F_{k}(x) converges

(iii) ∏_{k=0}^{∞}(1 + F_{k}(x)) converges

(i) ⇒ (ii) Let m ∈ ℕ_{0}. By (i), there exists an n_{0} ∈ ℕ such that ord F_{n}(x) > m for all n > n_{0}. It follows that

⟨x^{m}⟩ ∑_{k=0}^{n} F_{k}(x) = ⟨x^{m}⟩ ∑_{k=0}^{n_{0}} F_{k}(x)

for all n > n_{0}, as required.

(ii) ⇒ (i) Let m ∈ ℕ_{0}. For every m′ ≤ m, we have by (ii) the existence of an n_{0}(m′) ∈ ℕ such that for all n > n_{0}(m′),

⟨x^{m′}⟩ ∑_{k=0}^{n} F_{k}(x) = ⟨x^{m′}⟩ ∑_{k=0}^{n_{0}(m′)} F_{k}(x),

therefore we have ord F_{n}(x) ≠ m′ for all n > n_{0}(m′). It follows that ord F_{n}(x) > m if n > max{n_{0}(0), …, n_{0}(m)} =: n_{0}. Summarizing,

∀ m ∈ ℕ ∃ n_{0} ∈ ℕ ∀ n > n_{0} : ord F_{n}(x) > m,

as we wished to prove.

(i) ⇒ (iii) Let m ∈ ℕ_{0}. By (i), there exists an n_{0} ∈ ℕ such that ord F_{n}(x) > m for all n > n_{0}. By

⟨x^{m}⟩ ∏_{k=0}^{n+1}(1 + F_{k}(x)) = ⟨x^{m}⟩ ∏_{k=0}^{n}(1 + F_{k}(x)) + \underbrace{⟨x^{m}⟩ ∏_{k=0}^{n}(1 + F_{k}(x))F_{n+1}(x)}_{=0}

we get inductively that

⟨x^{m}⟩ ∏_{k=0}^{n} F_{k}(x) = ⟨x^{m}⟩ ∏_{k=0}^{n_{0}} F_{k}(x)

for all n > n_{0}.

(iii) ⇒ (i) Let m ∈ ℕ_{0}. For every m′ ≤ m, we have by (iii) the existence of an n_{0}(m′) ∈ ℕ such that for all n > n_{0}(m′),

⟨x^{m′}⟩ ∏_{k=0}^{n}(1 + F_{k}(x)) = ⟨x^{m′}⟩ ∏_{k=0}^{n_{0}(m′)}(1 + F_{k}(x)),  (1)

therefore we have ord F_{n}(x) ≠ m′ for all n > n_{0}(m′), for otherwise

⟨x^{m′}⟩ ∏_{k=0}^{n}(1 + F_{k}(x)) = ⟨x^{m′}⟩ ∏_{k=0}^{n−1}(1 + F_{k}(x)) + \underbrace{⟨x^{m′}⟩ \underbrace{F_{n}(x)}_{ord=m′} \underbrace{∏_{k=0}^{n−1}(1 + F_{k}(x))}_{ord=0}}_{≠0}

≠ ⟨x^{m′}⟩ ∏_{k=0}^{n−1}(1 + F_{k}(x))

in contradiction to (1). It follows again that ord F_{n}(x) > m for all n > max{n_{0}(0), …, n_{0}(m)} =: n_{0}. Summarizing, we get

∀ m ∈ ℕ ∃ n_{0} ∈ ℕ ∀ n > n_{0} : ord F_{n}(x) > m,

as we wished to prove.

Exercise 34 Prove Euler’s transform:

⟨x^{n}⟩\frac{1}{1 − x}u(\frac{x}{x − 1}) = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k}⟨x^{k}⟩u(x)

for u(x) ∈ ℂ[[x]] and n ∈ ℕ_{0}.

First note that ord \frac{x}{x−1} > 0. This allows the following computation, writing u(x) =

∑_{n=0}^{∞} u_{n}x^{n}:

\frac{1}{1 − x}u(\frac{x}{x − 1}) = ∑_{n=0}^{∞} x ∑_{n=0}^{∞} u_{n}( − x ∑_{k=0}^{∞} x^{k})^{n} = ∑_{n=0}^{∞} x( ∑_{n=0}^{∞}(−1)^{n}u_{n}x^{n} + c(x))

= ∑_{n=0}^{∞} x ∑_{n=0}^{∞}(−1)^{n}u_{n}x^{n} + \frac{c(x)}{1 − x}

= ∑_{n=0}^{∞} ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}u_{k} x^{n} + \frac{c(x)}{1 − x}

with some c(x) with ord c(x) > n. By ord \frac{c(x)}{1−x} = ord c(x) > n we get

⟨x^{n}⟩\frac{1}{1 − x}u(\frac{x}{x − 1}) = ⟨x^{n}⟩ ∑_{n=0}^{∞} ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}u_{k} x^{n} = ∑_{k=0}^{n} \binom{n}{k}(−1)^{k}u_{k}

as claimed.

Exercise 35 R := (ℂ[[x]], D) is a differential ring.

Let f(x) = ∑_{n=0}^{∞} f_{n}x^{n}, g(x) = ∑_{n=0}^{∞} g_{n}x^{n} ∈ ℂ[[x]]. Then

D(f(x) + g(x)) = D ∑_{n=0}^{∞}(f_{n} + g_{n})x^{n} = ∑_{n=0}^{∞}(f_{n+1} + g_{n+1})(n + 1)x^{n}

= ∑_{n=0}^{∞} f_{n+1}(n + 1)x^{n} + ∑_{n=0}^{∞} g_{n+1}(n + 1)x^{n} = Df(x) + Dg(x)

D(f(x) · g(x)) = D ∑_{n=0}^{∞} ∑_{k=0}^{n} \binom{n}{k}f_{k}g_{n−k}x^{n} = ∑_{n=0}^{∞} ∑_{k=0}^{n+1} \binom{n + 1}{k}f_{k}g_{n+1−k}(n + 1)x^{n}

= ∑_{n=0}^{∞} ∑_{k=0}^{n+1} \binom{n + 1}{k}(n + 1 − k + k)f_{k}g_{n+1−k}x^{n}

= ∑_{n=0}^{∞} ∑_{k=0}^{n+1} \binom{n + 1}{k}kf_{k}g_{n+1−k}x^{n}

+ ∑_{n=0}^{∞} ∑_{k=0}^{n+1} \binom{n + 1}{k}f_{k}(n + 1 − k)g_{n+1−k}x^{n}

= ∑_{n=0}^{∞}(n + 1)f_{n+1}x^{n} ∑_{n=0}^{∞} g_{n}x^{n} + ∑_{n=0}^{∞} f_{n}x^{n} ∑_{n=0}^{∞}(n + 1)g_{n+1}x^{n}

= (Df(x))g(x) + f(x)Dg(x).

Exercise 36 Let R = (R, D) be a differential ring.

a) C_{D}(R) is a subring of R.

b) for all u ∈ R, v ∈ R^{×} we have D \frac{u}{v} = \frac{(Du)v−uDv}{v^{2}} .

Ad a) If a, b ∈ C_{D}(R) then, by definition, Da = Db = 0, and consequently D(a + b) = Da + Db = 0 and D(ab) = (Da)b + aDb = 0.

Ad b) It suffices to show that D \frac{1}{v} = −\frac{1}{v^{2}} for v ∈ R^{×}. First, 1 ∈ C_{D}(R), because D1 = D(1 · 1) = (D1)1 + 1D1 = 2D1. (We assume characteristic zero; divisibility would be sufficient.) Now, 1 = v/v implies

0 = D1 = D(\frac{1}{v} v) = (D \frac{1}{v})v + \frac{1}{v} Dv

which in turn implies the claim.