Manuel Kauers Hagenberg, November 20, 2003 RISC-Linz

Analytic Combinatorics

Homework 7

Exercise 30 Let ε > 0 and let f, g be two functions which are analytic for |x| < ε,

f(x) = ∑_{n=0}^{∞} a_{n}x^{n}, g(x) = ∑_{n=0}^{∞} b_{n}x^{n} (|x| < ε).

Prove the transfer principle: If f(x) = g(x) (|x| < ε) then a_{n} = b_{n} (n ∈ ℕ_{0}).

For |x| < ε the convergence of the series of f and g is absolute, so we have

f(x) − g(x) = ∑_{n=0}^{∞} a_{n}x^{n} − ∑_{n=0}^{∞} b_{n}x^{n} = ∑_{n=0}^{∞}(a_{n} − b_{n})x^{n}

for those x. Assume the a_{n} and b_{n} do not agree for all n. Then there exists a minimal N ∈ ℕ_{0} with a_{N} ≠ b_{N}, and we can write

∑_{n=0}^{∞}(a_{n} − b_{n})x^{n} = ∑_{n=N}^{∞}(a_{n} − b_{n})x^{n} = x^{N} \underbrace{∑_{n=N}^{∞}(a_{n} − b_{n})x^{n−N}}_{=:c(x)} .

c is analytic because f and g are, and so c is in particular continuous. By a_{N} ≠ b_{N} we get c(0) ≠ 0, and continuity implies

∃ M > 0, δ > 0 ∀ |x| < δ : |c(x)| > M.

It follows

0 = |f(x) − g(x)| = |x^{N}c(x)| > M|x|^{N}

for all x with |x| < min\{ε, δ\} =: ε̃. For x = \frac{1}{2} ε̃ we get 0 > M(\frac{1}{2} ε̃)^{N} > 0. This is the desired contradiction.

Exercise 31 Prove

∑_{k=0}^{n} kk! = (n + 1)! − 1

Obvious by Δn! = (n + 1)! − n! = (n + 1 − 1)n! = nn!.

Exercise 32 Let f(x) ∈ ℂ[[x]] with f(0) = 0 and μ, λ ∈ ℂ. Prove

(1 + f(x))^{λ}(1 + f(x))^{μ} = (1 + f(x))^{λ+μ}

in ℂ[[x]].

It is known from analysis that the derivative obeys a binomial theorem of the form

(gh)^{(n)}(x) = ∑_{k=0}^{n} \binom{n}{k}g^{(n−k)}(x)h^{(k)}(x)  (g, h ∈ C^{∞}(ℂ), n ∈ ℕ_{0}).  (1)

Let λ, μ ∈ ℂ and consider g(x) = x^{λ}, h(x) = x^{μ}. Then g^{(n)}(x) = λ\underline{n}x^{λ−n}, h^{(n)}(x) = μ\underline{n}x^{μ−n}, (gh)^{(n)}(x) = (λ + μ)\underline{n}x^{λ+μ−n}. Plugging this into (1) and evaluating at x = 1 gives the binomial theorem for falling factorials,

(λ + μ)\underline{n} = ∑_{k=0}^{n} \binom{n}{k}λ\underline{n−k}μ\underline{k}  (λ, μ ∈ ℂ, n ∈ ℕ_{0}).  (2)

Note further that, by the definition of the binomial coefficient, we have

\binom{α}{n} = \frac{α\underline{n}}{n!}  (α ∈ ℂ, n ∈ ℕ_{0}).  (3)

Now:

(1 + f(x))^{λ}(1 + f(x))^{μ} =^{Def.} ∑_{n=0}^{∞} \binom{λ}{n}f(x)^{n} ∑_{n=0}^{∞} \binom{μ}{n}f(x)^{n}

= ∑_{n=0}^{∞} ∑_{k=0}^{n} \binom{λ}{k}\binom{μ}{n − k} f(x)^{n} =^{(3)} ∑_{n=0}^{∞} ∑_{k=0}^{n} \frac{n!}{n!} \frac{λ\underline{k}}{k!} \frac{μ\underline{n−k}}{(n − k)!} f(x)^{n}

= ∑_{n=0}^{∞} \frac{1}{n!} ∑_{k=0}^{n} \binom{n}{k}λ\underline{k}μ\underline{n−k} f(x)^{n} =^{(2)} ∑_{n=0}^{∞} \frac{1}{n!}(λ + μ)\underline{n} f(x)^{n}

=^{(3)} ∑_{n=0}^{∞} \binom{λ + μ}{n} f(x)^{n} =^{Def.} (1 + f(x))^{λ+μ}.