Manuel Kauers Hagenberg, November 5, 2003 RISC-Linz

Analytic Combinatorics

Homework 5

Exercise 14 Let p, q, r ∈ ℂ[x] and consider the difference equation

p(x) = q(x)y(x + 1) − r(x)y(x).  (∗)

Complete the degree analysis for the solution y of (∗) which was outlined in the lecture.

Let y = y_{d}x^{d}+y_{d−1}x^{d−1}+… be a solution of (∗). Here, and always in this solution, “… ” denotes a polynomial in x whose degree is strictly less than the degree of the term right in front of the dots. We may assume w.l.o.g. y_{d} ≠ 0, such that deg y = d. It is easily checked that (∗) can be rewritten as

2p(x) = (\underbrace{q(x) + r(x)}_{=:qr_{+}(x)})(y(x + 1) − y(x)) + (\underbrace{q(x) − r(x)}_{=:qr_{−}(x)})(y(x + 1) + y(x)) (1)

We write qr_{+} := q + r, qr_{−} := q − r, and we note that the binomial theorem implies

y(x + 1) − y(x) = y_{d}((x + 1)^{d} − x^{d}) + y_{d−1}((x + 1)^{d−1} − x^{d−1}) + \underbrace{. . . . . .}_{deg≤d−2}
= y_{d}(dx^{d−1} + …) + y_{d−1}((d − 1)x^{d−2} + …) + . . . . . .
= y_{d}dx^{d−1} + . . . . . .  (2)
y(x + 1) + y(x) = y_{d}((x + 1)^{d} + x^{d}) + … = 2y_{d}x^{d} + …  (3)

We distinguish cases, as indicated in the lecture. Case 1. deg qr_{+} ≤ deg qr_{−}. Then (1) implies

deg p = deg qr_{−}(y(x + 1) + y(x)) =^{(3)} deg qr_{−} + d,

and so d = deg p − deg qr_{−}. Case 2. deg qr_{+} > deg qr_{−}. Then we may write

qr_{+} = γx^{d′} + …, qr_{−} = βx^{d′−1} + …,

where γ ≠ 0 and β may or may not be zero. Plugging this and (2) and (3) into (1) gives

2p(x) = (γx^{d′} + …)(y_{d}dx^{d−1} + …) + (βx^{d′−1} + …)(2y_{d}x^{d} + …)
= (dγ + 2β)y_{d}x^{d+d′−1} + …  (4)

Consider α := −2β/γ. (Note that γ ≠ 0 by assumption.) Case 2a. α ∉ ℤ. Then γ ∤ −2β, i.e., dγ + 2β ≠ 0 for all d ∈ ℕ, especially for d = deg y. It follows that the leading coefficient of the right hand side of (4) does not vanish, and consequently we have deg p = d + d′ − 1, and finally

d = deg p − deg qr_{+} + 1.

Case 2b. α ∈ ℤ. Then γ | −2β, i.e., there is some n ∈ ℕ with nγ + 2β = 0. There are two possibilities.

(i) n = d. Then dγ + 2β = 0, i.e., d = −2β/γ = α. (ii) n ≠ d. Then dγ+2β ≠ 0 and reference to (4) shows that d = deg p−deg qr_{−}+1. In either case, d ≤ max{α, deg p − deg qr_{−} + 1} establishes the desired bound.

Exercise 15 Derive upper bounds for the solutions y of the second order difference equation

p(x) = a_{2}(x)y(x + 2) + a_{1}(x)y(x + 1) + a_{0}(x)y(x)  (∗∗)

where p, a_{2}, a_{1}, a_{0} ∈ ℂ[x] are given.

Let y = y_{d}x^{d} + y_{d−1}x^{d−1} + … be a solution to (∗∗). The meaning of “… ” is as in Exercise 14. As there, we assume w.l.o.g. y_{d} ≠ 0, such that deg y = d. It is easily checked that (∗∗) can be rewritten as

2p(x) = (\underbrace{a_{2}(x) + a_{1}(x) + a_{0}(x)}_{=:b_{1}(x)})(\underbrace{y(x + 1) + y(x)}_{=:y_{1}(x)})
+ (\underbrace{3a_{2}(x) + a_{1}(x) − a_{0}(x)}_{=:b_{2}(x)})(\underbrace{y(x + 1) − y(x)}_{=:y_{2}(x)})  (5)

+ (\underbrace{2a_{2}(x)}_{=:b_{3}(x)})(\underbrace{y(x + 2) − 2y(x + 1) + y(x)}_{=:y_{3}(x)})

(See the Appendix for how to find this representation.) Consider the degrees and leading coefficients of y_{i}. From the previous Exercise we know

y_{1}(x) = 2y_{d}x^{d} + …,  y_{2}(x) = dx^{d−1} + …  (6)

As for y_{3}, we note

(x + 2)^{n} − 2(x + 1)^{n} + x^{n} = (x^{n} + n2x^{n−1} + \binom{n}{2}4x^{n−2} + …)

− 2(x^{n} + nx^{n−1} + \binom{n}{2}x^{n−2} + …) + x^{n}

= 2\binom{n}{2}x^{n−2} + …

and conclude

y_{3}(x) = 2y_{d}\binom{d}{2}x^{d−2} + …  (7)

We distinguish the following cases. Case 1. deg b_{1} ≥ max(deg b_{2}, deg b_{3}). Then (6) and (7) in (5) give

deg p = deg(b_{1}y_{1} + b_{2}y_{2} + b_{3}y_{3}) = deg b_{1}y_{1} = deg b_{1} + d − 1

and hence d = deg p − deg b_{1} + 1. Case 2. deg b_{1} < max(deg b_{2}, deg b_{3}) =: d′.

Case 2a. deg b_{2} ≥ deg b_{3}. Then we may write

b_{1}(x) = β_{1}x^{d′−1} + …,
b_{2}(x) = β_{2}x^{d′} + …,
b_{3}(x) = β_{3}x^{d′} + …

with β_{2} ≠ 0. Plugging this into (5) and using (6) and (7) gives

2p(x) = (β_{1}x^{d′−1} + …)(2y_{d}x^{d} + …) + (β_{2}x^{d′} + …)(dy_{d}x^{d−1} + …)

+ (β_{3}x^{d′} + …)(2y_{d}\binom{d}{2}x^{d−2} + …)

= (2β_{1} + dβ_{2})y_{d}x^{d′+d−1} + …

Reasoning as in Exercise 14 gives d = deg p − deg b_{2} + 1 if α := 2β_{1}/β_{2} ∉ ℤ and d = max(α, deg p − deg b_{2} + 1) if α ∈ ℤ. Case 2b. deg b_{2} > deg b_{3}. Then we may write

b_{1}(x) = β_{1}x^{d′−1} + …,
b_{2}(x) = β_{2}x^{d′−1} + …,
b_{3}(x) = β_{3}x^{d′} + …

with β_{3} ≠ 0. Plugging this into (5) and using again (6) and (7) gives

2p(x) = (β_{1}x^{d′−1} + …)(2y_{d}x^{d} + …) + (β_{2}x^{d′−1} + …)(dy_{d}x^{d−1} + …)

+ (β_{3}x^{d′} + …)(2y_{d}\binom{d}{2}x^{d−2} + …)

= 2β_{1}y_{d}x^{d+d′−1} + d(β_{2} + (d − 1)β_{3})y_{d}x^{d+d′−2} + …

If β_{1} ≠ 0 then d = deg p − deg b_{2} + 1. Otherwise, if β_{1} = 0, then reasoning as in Exercise 14 gives d = deg p − deg b_{2} + 1 if α := (β_{2} − β_{3})/β_{3} ∉ ℤ and d = max(α, deg p − deg b_{2} + 1) if α ∈ ℤ.

Remark: Depending on a more clever choice of (5), one might arrive at a simpler case distinction.

Exercise 16 Check your favorite Computer Algebra system for the procedure call to solve such difference equations for polynomial solutions. Do they find all polynomial solutnions?

We quote from the Maple 8 help system entry for the function rsolve: “The procedure rsolve can currently solve linear recurrences with constant coefficients, systems of linear recurrences with constant coefficients, divide and conquer recurrences with constant coefficients, many first order linear recurrences, and some nonlinear first order recurrences.”

– That’s not too much…

Exercise 17 Give your favorite proof of the binomial theorem

(1 + y)^{n} = ∑_{m=0}^{n} \binom{n}{m}y^{m} (y ∈ ℂ, n ∈ ℕ_{0}).

It is not clear in this exercise what we are allowed to use. We assume the definition \binom{n}{m} = n!/m!(n − m)! and offer the following induction proof on n. As for the base case n = 1, we have

(1 + y)^{1} = 1 + y = ∑_{m=0}^{n} \binom{1}{m}y^{m}

because \binom{1}{0} = \binom{1}{1} = 1. Now suppose the equation holds for some n ∈ ℕ. We show that it holds for n + 1. We will need

\binom{n}{0} = \frac{n!}{0!n!} = 1 = \frac{(n + 1)!}{0!(n + 1)!} = \binom{n + 1}{0}  (8)
\binom{n}{n} = \frac{n!}{n!0!} = 1 = \frac{(n + 1)!}{(n + 1)!0!} = \binom{n + 1}{n + 1}  (9)
\binom{n}{m} + \binom{n}{m − 1} = \frac{n!}{m!(n − m)!} + \frac{n!}{(m − 1)!(n − m + 1)!}
= \frac{n!(n − m + 1) + n!m}{m!(n − m)!} = \binom{n + 1}{m}  (10)

in the following reasoning:

(1 + y)^{n+1} = (1 + y)^{n}(1 + y)

= ∑_{m=0}^{n} \binom{n}{m}y^{m}(1 + y)

= ∑_{m=0}^{n} \binom{n}{m}y^{m} + ∑_{m=0}^{n} \binom{n}{m}y^{m+1}

= ∑_{m=0}^{n} \binom{n}{m}y^{m} + ∑_{m=1}^{n+1} \binom{n}{m − 1}y^{m}

= ∑_{m=1}^{n} (\binom{n}{m} + \binom{n}{m − 1})y^{m} + \binom{n}{0} + \binom{n}{n}y^{n+1}

=^{(8),(9),(10)} ∑_{m=1}^{n} \binom{n + 1}{m}y^{m} + \binom{n + 1}{0} + \binom{n + 1}{n + 1}y^{n+1}

= ∑_{m=0}^{n+1} \binom{n + 1}{m}y^{m}.

Appendix

Just for fun, we want to mention how we found (5) using Maple. We want to write (∗∗) as a linear combination of y(x + 1) + y(x), y(x + 1) − y(x) = Δy(x), and y(x + 2) − 2y(x + 1) + y(x) = Δ^{2}y(x). We abreviate y_{0} = y(x), y_{1} = y(x + 1), y_{2} = y(x + 2) and a_{0} = a_{0}(x), a_{1} = a_{1}(x), a_{2} = a_{2}(x) and make an ansatz.

> p := a2*y2+a1*y1+a0*y0:
> q := A*(y1+y0) + B*(y1-y0) + C*(y2-2*y1+y0):

We want to find appropriate values for A, B, C, E such that Ep = q. First we solve for A.

> solve(q-E*p, A);

−\frac{By_{1} − By_{0} + Cy_{2} − 2Cy_{1} + Cy_{0} − Ea_{2}y_{2} − Ea_{1}y_{1} − Ea_{0}y_{0}}{y_{1} + y_{0}}

This ought to be a polynomial, i.e., the multivariate remainder of the numerator wrt. the denominator should vanish. What is this remainder in general?

> reduce(numer(%), [y1+y0], tdeg(y0,y1,y2));

−2By_{1} − Cy_{2} + 3Cy_{1} + Ea_{2}y_{2} + Ea_{1}y_{1} − Ea_{0}y_{1}

> collect(%, [y0,y1,y2]);

(−2B + 3C + Ea_{1} − Ea_{0})y_{1} + (Ea_{2} − C)y_{2}

This will for sure vanish if both the coefficients vanish. When is this the case?

> solve({coeffs(%, [y1,y2])});

\{a_{1} = a_{1}, a_{0} = a_{0}, a_{2} = a_{2}, C = Ea_{2}, B = \frac{1}{2}(Ea_{2} + Ea_{1} − Ea_{0}), E = E\}

This determines B and C.

> C := E*a2:
> B := E/2*(3*a2+a1-a0):

Having this fixed, we try again to solve for A.

> solve(q-E*p, A);

\frac{1}{2}E(a_{0} + a_{1} + a_{2})

As expected, this is now a polynomial. E is free, we choose E = 2 for avoiding fractions.

> E := 2:

The final result is then

> q;

(a_{0} + a_{1} + a_{2})(y_{1} + y_{0}) + (3a_{2} + a_{1} − a_{0})(y_{1} − y_{0}) + 2a_{2}(y_{2} − 2y_{1} + y_{0})

This is (5). We finally check the result:

> normal(q-E*p);

0