POLYNOMIAL PROBABILITY GENERATING FUNCTIONS WITH ALL ROOTS REAL

Di Warren School of Mathematics and Statistics, F07 University of Sydney, N.S.W. 2006 Australia

Abstract

The inherent difficulty in applying the Frobenius-Harper technique (Frobenius, 1910; Harper, 1967) to any setting, is proving that the roots of the polynomial p.g.f. are all real. We give two theorems providing sufficient conditions. This work supplies the technical proofs to Warren (1997).

Key words: generating function; real roots.

AMS 1991 subject classification: 60J10; 60C05; 60F05; 39A10

1 Introduction

Any non-negative integer-valued random variable with a polynomial p.g.f. with only real roots can be written as a sum of independent (not necessarily identically distributed) Bernoulli random variables. We call this property the Frobenius-Harper technique after the authors of the two seminal papers in which these ideas apparently first occur: Frobenius (1910); and Harper (1967). The inherent difficulty in applying the Frobenius-Harper technique to any setting, is proving that the roots of the polynomial p.g.f. are all real. To this end, we give the following two theorems, which we subsequently prove using three lemmas.

Theorem 1.1 Suppose that {X_{n}} (1 ≤ n < M = ∞ or 1 ≤ n ≤ M < ∞) is a sequence of random variables, where P (X_{n} = i) = P (n, i), i = d(n), d(n) + 1, …, f(n), where d(n) ≥ 0 is an integer which satisfies one of the following 2 conditions (though possibly not the same one for different j)

(1) d(j + 1) − d(j) = 0

(2) d(j + 1) − d(j) = 1 for j ≥ 1 (if M = ∞) or 1 ≤ j ≤ M − 1 (if M < ∞), and where f(n) ≥ d(n) + 1 is an integer which satisfies one of the following 2 conditions (though possibly not the same one for different j)

(1)′ f(j + 1) − f(j) = 0

(2)′ f(j + 1) − f(j) = 1 for j ≥ 1 (if M = ∞) or 1 ≤ j ≤ M − 1 (if M < ∞), and P (n, d(n)) > 0 and P (n, f(n)) > 0 (1 ≤ n ≤ M) and P (n, i) = 0 for i < d(n), i > f(n), n ≤ 0 and n > M (if M < ∞).

Suppose further that {X_{n}} gives rise to a sequence of p.g.f.s {G_{n}(t)} which satisfy

G_{n+1}(t) = a_{n}(t)G_{n}(t) + b_{n}(t)Gn^{′}(t),  (1)

for n ≥ 1 (if M = ∞) or 1 ≤ n ≤ M − 1 (if M < ∞), where a_{n}(t) and b_{n}(t) are continuous functions on tϵ(−∞, ∞).

If for some m ≥ 1 (if M = ∞) or 1 ≤ m ≤ M − 1 (if M < ∞) the f(m) − d(m) non-zero roots of G_{m}(t) are all real and single and also b_{n}(t) < 0 for all t < 0 and for n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞), then the f(n) − d(n) non-zero roots of G_{n}(t) are all real, single (or distinct) and negative for all n ≥ m (if M = ∞) or m ≤ n ≤ M (if M < ∞).

Theorem 1.2 Suppose that {X_{n}} (1 ≤ n < M = ∞ or 1 ≤ n ≤ M < ∞) is a sequence of random variables satisfying the condition of Theorem 1.1, except that f(n) > d(n) + 1. Assume further that for some m ≥ 1 (if M = ∞) or 1 ≤ m ≤ M − 1 (if M < ∞) the f(m) − d(m) > 1 non-zero roots of G_{m}(t) are all real, and denoted by {r_{i}^{(m)}} where −∞ < r_{1}^{(m)} ≤ … ≤ r_{f(m)−d(m)}^{(m)} < 0. Suppose also that these roots are all single, except for r_{q}^{(m)} (1 ≤ q ≤ f(m) − d(m) − c(m) + 1) which is a multiple root of order c(m). Further suppose that bn^{′}(ξ) exists for all ξ, r_{q}^{(m)} < ξ < t < 0, for n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞).

Then: (A) If b_{n}(r_{q}^{(m)}) = 0 for each n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞), then r_{q}^{(m)} is a multiple root of G_{n}(t) of order c(n) for all n ≥ m (if M = ∞) or m ≤ n ≤ M (if M < ∞), and c(n + 1) ≥ c(n) for all n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞). (B1) Suppose q = 1. If b_{n}(r_{1}^{(m)}) = 0 and b_{n}(t) < 0 for r_{1}^{(m)} < t < 0 for each n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞), then for n ≥ m (if M = ∞) or m ≤ n ≤ M (if M < ∞), r_{1}^{(m)} is the smallest root of G_{n}(t) and any non-zero roots other than r_{1}^{(m)}, are real and single. Also, c(n + 1) − c(n) = 0 or 1 for all n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞). (B2) Suppose q > 1. If b_{n}(r_{q}^{(m)}) = 0 and b_{n}(t) < 0 for t < 0∩t ≠ r_{q}^{(m)} for each n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞), then for n ≥ m (if M = ∞) or m ≤ n ≤ M (if M < ∞), any non-zero roots of G_{n}(t) other than r_{q}^{(m)}, are real and single. Also, c(n + 1) − c(n) = 0 or 1 for all n ≥ m (if M = ∞) or m ≤ n ≤ M − 1 (if M < ∞).

2 Three Important Lemmas

Lemma 2.1 Suppose that for n ≥ 1, G_{n}(t) is a p.g.f. ∑_{x=d(n)}^{f(n)} p_{n,x}t^{x} where 0 ≤ d(n) < f(n), p_{n,d(n)} > 0 and p_{n,f(n)} > 0. Suppose further that the roots are all real and are denoted by {r_{i}^{(n)}}, where −∞ < r_{1}^{(n)} ≤ … ≤ r_{f(n)−d(n)}^{(n)} < 0; and r_{f(n)−d(n)+1}^{(n)} = … = r_{f(n)}^{(n)} = 0, if d(n) ≥ 1.

(i) If r_{1}^{(n)} is a single root, then Gn^{′}(r_{1}^{(n)}) has the opposite sign to G_{n}(−∞). In addition, if r_{2}^{(n)} is also a single root, then Gn^{′}(r_{2}^{(n)}) has the same sign as G_{n}(−∞).

(ii) If r_{i}^{(n)} is a single root, then Gn^{′}(r_{i}^{(n)}) has the same sign as G_{n}(r_{i+1}^{(n)−}) (for 1 ≤ i ≤ f(n) − 1 if d(n) = 0, for 1 ≤ i ≤ f(n) − d(n) if d(n) ≥ 1). In addition, if r_{i+1}^{(n)} is also a single root, then G_{n}(r_{i}^{(n)+}) has the opposite sign to Gn^{′}(r_{i+1}^{(n)}) (for 1 ≤ i ≤ f(n) − d(n) − 1).

(iii) If r_{i}^{(n)} is a multiple root of order c(n) (c(n) + d(n) + 1 ≤ f(n)) and r_{i+c(n)}^{(n)} is a single root, then G_{n}(r_{i}^{(n)+}) has the opposite sign to Gn^{′}(r_{i+c(n)}^{(n)}) (for 1 ≤ i ≤ f(n) − d(n) − c(n)).

(iv) If r_{i}^{(n)} is a multiple root of order c(n) (c(n)+d(n)+2 ≤ f(n)) and r_{i−1}^{(n)} and r_{i+c(n)}^{(n)} are single roots, then Gn^{′}(r_{i−1}^{(n)}) has the opposite sign to Gn^{′}(r_{i+c(n)}^{(n)}) (if c(n) is even) and Gn^{′}(r_{i−1}^{(n)}) has the same sign as Gn^{′}(r_{i+c(n)}^{(n)}) (if c(n) is odd) (for 2 ≤ i ≤ f(n)−d(n)−c(n)).

Lemma 2.2 Let {X_{n}}, n ≥ 1 be a sequence of non-negative, integer-valued random variables, where P (X_{n} = x) = p_{n,x}, x = d(n), d(n) + 1, …, f(n), where d(n) and f(n) are integers and 0 ≤ d(n) < f(n), p_{n,d(n)} > 0 and p_{n,f(n)} > 0. Denote the p.g.f. of X_{n} by G_{n}(t) = ∑_{x=d(n)}^{f(n)} p_{n,x}t^{x} and suppose that {G_{n}(t)} satisfies (1) where a_{n}(t) and b_{n}(t) are continuous functions for tϵ(−∞, ∞).

Suppose that the f(n) roots of G_{n}(t) are all real and are denoted by {r_{i}^{(n)}, i = 1, …, f(n)}, where −∞ < r_{1}^{(n)} ≤ … ≤ r_{f(n)−d(n)}^{(n)} < 0; and r_{f(n)−d(n)+1}^{(n)} = … = r_{f(n)}^{(n)} = 0, if d(n) ≥ 1.

(i) If r_{i}^{(n)} and r_{i+1}^{(n)} are both single roots and b_{n}(r_{i}^{(n)}) < 0 and b_{n}(r_{i+1}^{(n)}) < 0 (1 ≤ i ≤ f(n) − d(n) − 1), then there is at least one root of G_{n+1}(t) in (r_{i}^{(n)}, r_{i+1}^{(n)}).

(ii) Suppose that r_{1}^{(n)} is a single root and that f(n + 1) = f(n) + 1. If b_{n}(r_{1}^{(n)}) < 0, then there is a root of G_{n+1}(t) in (−∞, r_{1}^{(n)}). If b_{n}(r_{1}^{(n)}) = 0 and b_{n}(r_{2}^{(n)}) < 0 where r_{2}^{(n)} is a single root, then there is at least one root of G_{n+1}(t) in either (−∞, r_{1}^{(n)}) or (r_{1}^{(n)}, r_{2}^{(n)}) or a multiple root of order 2 at r_{1}^{(n)}.

(iii) Suppose that r_{1}^{(n)} is a multiple root of order c(n) (c(n) + d(n) + 1 ≤ f(n)) and that r_{1}^{(n+1)} = r_{1}^{(n)} and is a multiple root of order c(n + 1), where c(n + 1) = c(n) and f(n + 1) = f(n) + 1. If b_{n}(r_{c(n)+1}^{(n)}) < 0 where r_{c(n)+1}^{(n)} is a single root, then there is at least one root of G_{n+1}(t) in (r_{1}^{(n)}, r_{c(n)+1}^{(n)}).

(iv) Suppose that r_{1}^{(n)} is a multiple root of order c(n) (c(n) + d(n) = f(n)) and that r_{1}^{(n+1)} = r_{1}^{(n)} and is a multiple root of order c(n + 1), where c(n + 1) = c(n) and d(n + 1) = d(n) and f(n + 1) = f(n) + 1. Then, there is precisely one root of G_{n+1}(t) in (r_{1}^{(n)}, 0).

(v) Suppose that r_{i}^{(n)} (2 ≤ i ≤ f(n) − d(n) − c(n)) is a multiple root of order c(n) (c(n) + d(n) + 2 ≤ f(n)) and is also a multiple root of G_{n+1}(t) of order c(n + 1), where c(n+1) = c(n). If b_{n}(r_{i−1}^{(n)}) < 0 and b_{n}(r_{i+c(n)}^{(n)}) < 0 where r_{i−1}^{(n)} and r_{i+c(n)}^{(n)} are both single roots, then there is at least one root of G_{n+1}(t) in either (r_{i−1}^{(n)}, r_{i}^{(n)}) or (r_{i}^{(n)}, r_{i+c(n)}^{(n)}).

(vi) Suppose that r_{f(n)−d(n)}^{(n)} (the nearest non-zero root to zero) is a single root and that d(n + 1) = d(n). If b_{n}(r_{f(n)−d(n)}^{(n)}) < 0, then there is at least one root of G_{n+1}(t) in (r_{f(n)−d(n)}^{(n)}, 0).

(vii) Suppose that r_{f(n)−d(n)−c(n)+1}^{(n)} (the nearest non-zero root to zero) is a multiple root of order c(n) and a multiple root of order c(n+1) of G_{n+1}(t), where c(n+1) = c(n) and d(n + 1) = d(n). If b_{n}(r_{f(n)−d(n)−c(n)}^{(n)}) < 0 where r_{f(n)−d(n)−c(n)}^{(n)} is a single root, then there is at least one root of G_{n+1}(t) in (r_{f(n)−d(n)−c(n)}^{(n)}, r_{f(n)−d(n)−c(n)+1}^{(n)}).

Lemma 2.3 Let {X_{n}}, n ≥ 1 be a sequence of non-negative, integer-valued random variables, where P (X_{n} = x) = p_{n,x}, x = d(n), d(n) + 1, …, f(n), where d(n) and f(n) are integers and 0 ≤ d(n) < f(n), p_{n,d(n)} > 0 and p_{n,f(n)} > 0. Denote the p.g.f. of X_{n} by G_{n}(t) = ∑_{x=d(n)}^{f(n)} p_{n,x}t^{x} and suppose that {G_{n}(t)} satisfies (1) where a_{n}(t) and b_{n}(t) are continuous functions on tϵ(−∞, ∞), and Suppose also that bn^{′}(ξ) exists for all ξ < 0, for each n.

Suppose that the f(n) roots of G_{n}(t) are all real and are denoted by {r_{i}^{(n)}, i = 1, …, f(n)}, where −∞ < r_{1}^{(n)} ≤ … ≤ r_{f(n)−d(n)}^{(n)} < 0 and r_{f(n)−d(n)+1}^{(n)} = … = r_{f(n)}^{(n)} = 0, if d(n) ≥ 1.

(i) If the non-zero roots of G_{n}(t) are all single, and b_{n}(0) = 0 and b_{n}(t) < 0 for all t < 0, then d(n + 1) ≥ d(n) and f(n + 1) ≥ f(n).

(ii) If the non-zero roots of G_{n}(t) are all single, except for a multiple root of order c(n) at r_{q}^{(n)} (1 ≤ q ≤ f(n) − d(n) − c(n) + 1), and b_{n}(0) = b_{n}(r_{q}^{(n)}) = 0 and b_{n}(t) < 0 for all t < 0 ∩ t ≠ r_{q}^{(n)}, then r_{q}^{(n)} is a multiple root of G_{n+1}(t) of order c(n + 1) where c(n + 1) ≥ c(n), and d(n + 1) ≥ d(n) and f(n + 1) ≥ f(n).

3 Proofs of Three Lemmas

Proof of Lemma 2.1

(i) For small δ > 0, G_{n}(−∞) has the same sign as G_{n}(r_{1}^{(n)}−δ) (as r_{1}^{(n)} is the smallest root of G_{n}(t)). Now G_{n}(t) = (t−r_{1}^{(n)})H_{n}(t) for some H_{n}(t), where H_{n}(r_{1}^{(n)}) ≠ 0 (as r_{1}^{(n)} is a single root). So G_{n}(r_{1}^{(n)}−δ) = −δH_{n}(r_{1}^{(n)}−δ) which means that G_{n}(r_{1}^{(n)}−δ) has the opposite sign to H_{n}(r_{1}^{(n)} −δ) (as δ > 0). But H_{n}(r_{1}^{(n)} −δ) has the same sign as H_{n}(r_{1}^{(n)}) (from the continuity of H_{n}(t) at r_{1}^{(n)}, as H_{n}(r_{1}^{(n)}) ≠ 0). Also, Gn^{′}(r_{1}^{(n)}) = H_{n}(r_{1}^{(n)}), so H_{n}(r_{1}^{(n)}) has the same sign as Gn^{′}(r_{1}^{(n)}) . Therefore, G_{n}(−∞) has the opposite sign to

Gn^{′}(r_{1}^{(n)}).

Now Gn^{′}(r_{1}^{(n)}) has the opposite sign to Gn^{′}(r_{2}^{(n)}) (as r_{1}^{(n)} and r_{2}^{(n)} are distinct, successive, single roots), therefore Gn^{′}(r_{2}^{(n)}) has the same sign as G_{n}(−∞).

(ii) For small δ > 0, G_{n}(r_{i+1}^{(n)−}) has the same sign as G_{n}(r_{i}^{(n)} + δ) (as r_{i}^{(n)} and r_{i+1}^{(n)} are successive, single, real roots). Now G_{n}(t) = (t − r_{i}^{(n)})H_{n}(t) for some H_{n}(t), where H_{n}(r_{i}^{(n)}) ≠ 0 (as r_{i}^{(n)} is a single root). So G_{n}(r_{i}^{(n)} + δ) = δH_{n}(r_{i}^{(n)} + δ) which means that G_{n}(r_{i}^{(n)} + δ) has the same sign as H_{n}(r_{i}^{(n)} + δ) (as δ > 0). But H_{n}(r_{i}^{(n)} + δ) has the same sign as H_{n}(r_{i}^{(n)}) (from the continuity of H_{n}(t) at r_{i}^{(n)}, as H_{n}(r_{i}^{(n)}) ≠ 0). Also, Gn^{′}(r_{i}^{(n)}) = H_{n}(r_{i}^{(n)}), so H_{n}(r_{i}^{(n)}) has the same sign as Gn^{′}(r_{i}^{(n)}) . Therefore, G_{n}(r_{i+1}^{(n)−}) has the same sign as Gn^{′}(r_{i}^{(n)}).

For small δ > 0, G_{n}(r_{i}^{(n)+}) has the same sign as G_{n}(r_{i+1}^{(n)} − δ) (as r_{i}^{(n)} and r_{i+1}^{(n)} are successive, single, real roots). Now G_{n}(t) = (t − r_{i+1}^{(n)})H_{n}(t) for some H_{n}(t), where H_{n}(r_{i+1}^{(n)}) ≠ 0 (as r_{i+1}^{(n)} is a single root). So G_{n}(r_{i+1}^{(n)} − δ) = −δH_{n}(r_{i+1}^{(n)} − δ) which means that G_{n}(r_{i+1}^{(n)} − δ) has the opposite sign to H_{n}(r_{i+1}^{(n)} − δ) (as δ > 0). But H_{n}(r_{i+1}^{(n)} − δ) has the same sign as H_{n}(r_{i+1}^{(n)}) (from the continuity of H_{n}(t) at r_{i+1}^{(n)}, as H_{n}(r_{i+1}^{(n)}) ≠ 0). Also, Gn^{′}(r_{i+1}^{(n)}) = H_{n}(r_{i+1}^{(n)}), so H_{n}(r_{i+1}^{(n)}) has the same sign as Gn^{′}(r_{i+1}^{(n)}) . Therefore, G_{n}(r_{i}^{(n)+}) has the opposite sign to Gn^{′}(r_{i+1}^{(n)}).

(iii) For small δ > 0, G_{n}(r_{i}^{(n)+}) has the same sign as G_{n}(r_{i+c(n)}^{(n)} − δ) (as r_{i}^{(n)} and r_{i+c(n)}^{(n)} are successive, single, real roots). Now G_{n}(t) = (t−r_{i+c(n)}^{(n)})H_{n}(t) for some H_{n}(t), where H_{n}(r_{i+c(n)}^{(n)}) ≠ 0 (as r_{i+c(n)}^{(n)} is a single root). So G_{n}(r_{i+c(n)}^{(n)}−δ) = −δH_{n}(r_{i+c(n)}^{(n)}−δ) which means that G_{n}(r_{i+c(n)}^{(n)} − δ) has the opposite sign to H_{n}(r_{i+c(n)}^{(n)} − δ) (as δ > 0). But H_{n}(r_{i+c(n)}^{(n)} − δ) has the same sign as H_{n}(r_{i+c(n)}^{(n)}) (from the continuity of H_{n}(t) at

r_{i+c(n)}^{(n)}, as H_{n}(r_{i+c(n)}^{(n)}) ≠ 0). Also, Gn^{′}(r_{i+c(n)}^{(n)}) = H_{n}(r_{i+c(n)}^{(n)}), so H_{n}(r_{i+c(n)}^{(n)}) has the same

sign as Gn^{′}(r_{i+c(n)}^{(n)}) . Therefore, G_{n}(r_{i}^{(n)+}) has the opposite sign to Gn^{′}(r_{i+c(n)}^{(n)}).

(iv) Since G_{n}(t) = (t − r_{i}^{(n)})^{c(n)}H_{n}(t) for some H_{n}(t) where H_{n}(r_{i}^{(n)}) ≠ 0, G_{n}(r_{i}^{(n)−}) has the same sign as G_{n}(r_{i}^{(n)+}) (when c(n) is even) and G_{n}(r_{i}^{(n)−}) has the opposite sign to G_{n}(r_{i}^{(n)+}) (when c(n) is odd). Now from (i), we know that Gn^{′}(r_{i−1}^{(n)}) has the same sign as G_{n}(r_{i}^{(n)−}) and from (ii), G_{n}(r_{i}^{(n)+}) has the opposite sign to Gn^{′}(r_{i+c(n)}^{(n)}). So clearly, Gn^{′}(r_{i−1}^{(n)}) has the opposite sign to Gn^{′}(r_{i+c(n)}^{(n)}) (if c(n) is even) and Gn^{′}(r_{i−1}^{(n)}) has the same sign as Gn^{′}(r_{i+c(n)}^{(n)}) (if c(n) is odd).

Proof of Lemma 2.2

(i) From (1), we note that G_{n+1}(r_{i}^{(n)}) = b_{n}(r_{i}^{(n)})Gn^{′}(r_{i}^{(n)}) and G_{n+1}(r_{i+1}^{(n)}) = b_{n}(r_{i+1}^{(n)})Gn^{′}(r_{i+1}^{(n)})

(as G_{n}(r_{i}^{(n)}) = G_{n}(r_{i+1}^{(n)}) = 0). But b_{n}(r_{i}^{(n)}) < 0 and b_{n}(r_{i+1}^{(n)}) < 0 and Gn^{′}(r_{i}^{(n)}) and

Gn^{′}(r_{i+1}^{(n)}) have opposite signs (as r_{i}^{(n)} and r_{i+1}^{(n)} are successive, single, real roots), so G_{n+1}(r_{i}^{(n)}) and G_{n+1}(r_{i+1}^{(n)}) will have opposite signs. Therefore, there must be at least one root (more precisely: an odd number of roots) of G_{n+1}(t) within the interval (r_{i}^{(n)}, r_{i+1}^{(n)}).

(ii) G_{n+1}(r_{1}^{(n)}) is non-zero and has the opposite sign to Gn^{′}(r_{1}^{(n)}) (by (1), as b_{n}(r_{1}^{(n)}) < 0 where r_{1}^{(n)} is a single root), which has the opposite sign to G_{n}(−∞) (by Lemma 2.1 (i)). But G_{n+1}(−∞) has the opposite sign to G_{n}(−∞) (as f(n + 1) = f(n) + 1). Therefore, G_{n+1}(r_{1}^{(n)}) has the opposite sign to G_{n+1}(−∞) and so there is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}).

In the second part, G_{n+1}(r_{2}^{(n)}) has the opposite sign to Gn^{′}(r_{2}^{(n)}) (by (1), as b_{n}(r_{2}^{(n)}) < 0 where r_{2}^{(n)} is a single root), which has the same sign as G_{n}(−∞) (by Lemma 2.1 (i), as r_{1}^{(n)} and r_{2}^{(n)} are single roots). Again, G_{n+1}(−∞) has the opposite sign to G_{n}(−∞) (as f(n + 1) = f(n) + 1). Therefore, G_{n+1}(−∞) has the same sign as G_{n+1}(r_{2}^{(n)}), and G_{n+1}(r_{1}^{(n)}) = 0 (by (1), as b_{n}(r_{1}^{(n)}) = 0), so there is at least one root of G_{n+1}(t) in either (−∞, r_{1}^{(n)}) or (r_{1}^{(n)}, r_{2}^{(n)}) or a double root at r_{1}^{(n)}.

(iii) G_{n+1}(r_{c(n)+1}^{(n)}) has the opposite sign to Gn^{′}(r_{c(n)+1}^{(n)}) (from (1), as b_{n}(r_{c(n)+1}^{(n)}) < 0 where r_{c(n)+1}^{(n)} is a single root), which is the opposite sign to G_{n}(r_{1}^{(n)+}) (by Lemma 2.1 (iii)). But G_{n}(r_{1}^{(n)+}) has the opposite sign to G_{n+1}(r_{1}^{(n)+}) (as f(n + 1) = f(n) + 1 and c(n + 1) = c(n)). Therefore, G_{n+1}(r_{c(n)+1}^{(n)}) has the opposite sign to G_{n+1}(r_{1}^{(n)+}), so there is at least one root of G_{n+1}(t) in (r_{1}^{(n)}, r_{c(n)+1}^{(n)}).

(iv) Since c(n + 1) = c(n), d(n + 1) = d(n) and f(n + 1) = f(n) + 1, there must be another non-zero real root, and it must differ from r_{1}^{(n)}, hence it must lie strictly between r_{1}^{(n)} and 0.

(v) If c(n) is even, then Gn^{′}(r_{i−1}^{(n)}) and Gn^{′}(r_{i+c(n)}^{(n)}) will have opposite signs (from Lemma 2.1 (iv)), so G_{n+1}(r_{i−1}^{(n)}) and G_{n+1}(r_{i+c(n)}^{(n)}) will have opposite signs (from (1), as b_{n}(r_{i−1}^{(n)}) < 0 and b_{n}(r_{i+c(n)}^{(n)}) < 0 where r_{i−1}^{(n)} and r_{i+c(n)}^{(n)} are single roots). Now as c(n+1) = c(n), G_{n+1}(r_{i}^{(n)−}) and G_{n+1}(r_{i}^{(n)+}) will have the same sign (as c(n) is even), so there is at least one real root of G_{n+1}(t) in either (r_{i−1}^{(n)}, r_{i}^{(n)}) or (r_{i}^{(n)}, r_{i+c(n)}^{(n)}). Similarly, is c(n) is odd, then Gn^{′}(r_{i−1}^{(n)}) and Gn^{′}(r_{i+c(n)}^{(n)}) will have the same sign (from Lemma 2.1 (iv)), so G_{n+1}(r_{i−1}^{(n)}) and G_{n+1}(r_{i+c(n)}^{(n)}) will have the same sign (from (1), as b_{n}(r_{i−1}^{(n)}) < 0 and b_{n}(r_{i+c(n)}^{(n)}) < 0 where r_{i−1}^{(n)} and r_{i+c(n)}^{(n)} are single roots). Now as c(n + 1) = c(n), G_{n+1}(r_{i}^{(n)−}) and G_{n+1}(r_{i}^{(n)+}) will have opposite signs (as c(n) is odd), so there is at least one root of G_{n+1}(t) in either (r_{i−1}^{(n)}, r_{i}^{(n)}) or (r_{i}^{(n)}, r_{i+c(n)}^{(n)}).

(vi) First, suppose that d(n) ≥ 1. G_{n+1}(r_{f(n)−d(n)}^{(n)}) has the opposite sign to Gn^{′}(r_{f(n)−d(n)}^{(n)})

(by (1), as b_{n}(r_{f(n)−d(n)}^{(n)}) < 0 where r_{f(n)−d(n)}^{(n)} is a single root), which has the same sign as G_{n}(0^{−}) (by Lemma 2.1 (ii), as d(n) ≥ 1). But G_{n+1}(0^{−}) has the same sign as G_{n}(0^{−}) (as d(n + 1) = d(n)). Therefore G_{n+1}(r_{f(n)−d(n)}^{(n)}) has the opposite sign to G_{n+1}(0^{−}) and so there is at least one root of G_{n+1}(t) in (r_{f(n)−d(n)}^{(n)}, 0).

Next, suppose that d(n) = 0, so r_{f(n)−d(n)}^{(n)} = r_{f(n)}^{(n)}. Now G_{n+1}(r_{f(n)}^{(n)}) < 0 (from (1), as Gn^{′}(r_{f(n)}^{(n)}) > 0 since r_{f(n)}^{(n)} is the last root and is single, and b_{n}(r_{f(n)}^{(n)}) < 0) and G_{n+1}(0) > 0 (as G_{n+1}(0) = p_{n+1,0} = p_{n+1,d(n+1)} > 0, as d(n + 1) = d(n) = 0), so there is at least one root of G_{n+1}(t) in (r_{f(n)}^{(n)}, 0).

(vii) Gn^{′}(r_{f(n)−d(n)−c(n)}^{(n)}) has the same sign as G_{n}(r_{f(n)−d(n)−c(n)+1}^{(n)−}) (by Lemma 2.1

(ii)). But G_{n+1}(r_{f(n)−d(n)−c(n)}^{(n)}) has the opposite sign to Gn^{′}(r_{f(n)−d(n)−c(n)}^{(n)}) (by (1), as

b_{n}(r_{f(n)−d(n)−c(n)}^{(n)}) < 0 where r_{f(n)−d(n)−c(n)}^{(n)} is a single root), and G_{n+1}(r_{f(n)−d(n)−c(n)+1}^{(n)−}) has the same sign as G_{n}(r_{f(n)−d(n)−c(n)+1}^{(n)−}) (as d(n + 1) = d(n) and c(n + 1) = c(n)), so G_{n+1}(r_{f(n)−d(n)−c(n)}^{(n)}) has the opposite sign to G_{n+1}(r_{f(n)−d(n)−c(n)+1}^{(n)}). Therefore, there is at least one root of G_{n+1}(t) in (r_{f(n)−d(n)−c(n)}^{(n)}, r_{f(n)−d(n)−c(n)+1}^{(n)}).

Proof of Lemma 2.3

(i) If d(n) = 0, then clearly d(n + 1) ≥ d(n) (as d(n + 1) ≥ 0). If d(n) ≥ 1, then G_{n}(t) = t^{d(n)}H_{n}(t) for some polynomial H_{n}(t) where H_{n}(0) ≠ 0. Therefore, Gn^{′}(t) = t^{d(n)−1} (d(n)H_{n}(t) + tHn^{′}(t)). Now from the continuity and differentibility assumptions on b_{n}(t), the Mean Value Theorem gives b_{n}(t) = b_{n}(0) + tbn^{′}(ξ_{t}), where ξ_{t} is strictly between t and 0. But b_{n}(0) = 0, so b_{n}(t) = tbn^{′}(ξ_{t}).

Substituting the expressions for G_{n}(t), Gn^{′}(t) and b_{n}(t) in (1), we get

G_{n+1}(t) = t^{d(n)} (a_{n}(t)H_{n}(t) + bn^{′}(ξ_{t}) (d(n)H_{n}(t) + tHn^{′}(t))) .

Hence 0 is a root of G_{n+1}(t) of order d(n + 1) ≥ d(n).

Firstly, suppose that d(n) + 1 = f(n) (i.e. there is only one non-zero root, a single root, at r_{1}^{(n)}). There is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}) (if f(n + 1) = f(n) + 1, from Lemma 2.2(ii)) and in (r_{1}^{(n)}, 0) (if d(n + 1) = d(n), from Lemma 2.2(vi), as r_{f(n)−d(n)}^{(n)} = r_{1}^{(n)}). Adding the d(n + 1) roots at 0, we have accounted for I_{(f(n+1)=f(n)+1)} + I_{(d(n+1)=d(n))} + d(n + 1) of the roots of G_{n+1}(t). This has a lower bound of I_{(f(n+1)=f(n)+1)} + d(n) + 1 (as d(n + 1) ≥ d(n)) which is I_{(f(n+1)=f(n)+1)} + f(n) (as d(n) + 1 = f(n)). Therefore, f(n + 1) ≥ f(n).

Secondly, suppose that d(n) + 1 < f(n) (i.e. there is more than one single root less than 0). Again, there is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}) (if f(n+1) = f(n)+1) and in (r_{f(n)−d(n)}^{(n)}, 0) (if d(n + 1) = d(n)), plus at least one root of G_{n+1}(t) in each of the intervals (r_{1}^{(k)}, r_{2}^{(k)}), (r_{2}^{(k)}, r_{3}^{(k)}), …, (r_{f(n)−d(n)−1}^{(k)}, r_{f(n)−d(n)}^{(k)}) (from Lemma 2.2(i), as b_{n}(t) < 0 for all t < 0). Adding the d(n + 1) roots at 0, we have accounted for I_{(f(n+1)=f(n)+1)} + I_{(d(n+1)=d(n))} + f(n) − d(n) − 1 + d(n + 1) ^{1} of the roots of G_{n+1}(t). This can be rewritten as I_{(f(n+1)=f(n)+1)} + f(n) + (d(n + 1) − d(n) + I_{(d(n+1)=d(n))} − 1) which has a lower bound of I_{(f(n+1)=f(n)+1)} + f(n) (as d(n + 1) ≥ d(n)), which is the expression above, so again f(n + 1) ≥ f(n).

(ii) We have already shown that d(n + 1) ≥ d(n) (as b_{n}(0) = 0). Using the same method, with 0 replaced by r_{q}^{(n)}, we can show that r_{q}^{(n)} is a multiple root of G_{n+1}(t) of order c(n + 1) ≥ c(n) (as b_{n}(r_{q}^{(n)}) = 0).

I: Suppose that q = 1.

Firstly, suppose that c(n) + d(n) = f(n) (that is, there are no single, real, nonzero roots of G_{n}(t)). There are c(n + 1) roots of G_{n+1}(t) at r_{1}^{(n)} and d(n + 1) roots at 0 and a root in (r_{1}^{(n)}, 0) (if c(n + 1) = c(n), d(n + 1) = d(n) and f(n + 1) = f(n) + 1, from Lemma 2.2(iv)), which accounts for at least c(n + 1) + d(n + 1) + I_{(c(n+1)=c(n),d(n+1)=d(n),f(n+1)=f(n)+1)} roots of G_{n+1}(t). But c(n+1) ≥ c(n) and d(n+1) ≥ d(n), so this has a lower bound of c(n) + d(n) + I_{(c(n+1)=c(n),d(n+1)=d(n),f(n+1)=f(n)+1)}, which reduces to f(n) + I_{(c(n+1)=c(n),d(n+1)=d(n),f(n+1)=f(n)+1)} (as c(n) + d(n) = f(n)). Clearly, f(n + 1) ≥ f(n).

1Note that this equation actually holds for the previous case: where f(n) − d(n) − 1 = 0.

Secondly, suppose that c(n) + d(n) + 1 = f(n) (i.e. there is one single, real, nonzero root r_{c(k)+1}^{(k)} of G_{n}(t), which is greater than r_{1}^{(n)}). There is at least one real root of G_{n+1}(t) in (r_{1}^{(n)}, r_{c(n)+1}^{(n)}) (if f(n+1) = f(n)+1 and c(n+1) = c(n), from Lemma 2.2(iii)) and in (r_{c(n)+1}^{(n)}, 0) (if d(n + 1) = d(n), from Lemma 2.2(vi), as r_{c(n)+1}^{(n)} = r_{f(n)−d(n)}^{(n)}). Adding the c(n + 1) roots at r_{1}^{(n)} and d(n + 1) roots at 0, we have accounted for I_{(f(n+1)=f(n)+1,c(n+1)=c(n))} + I_{(d(n+1)=d(n))} + c(n + 1) + d(n + 1) roots of G_{n+1}(t). But c(n + 1) ≥ c(n) and d(n + 1) ≥ d(n), so this has a lower bound of c(n) + d(n) + 1 + I_{(c(n+1)=c(n),d(n+1)=d(n),f(n+1)=f(n)+1)}, which reduces to f(n) + I_{(f(n+1)=f(n)+1,c(n+1)=c(n))} (as c(n) + d(n) + 1 = f(n)). Again, f(n + 1) ≥ f(n).

Finally, suppose that c(n) + d(n) + 1 < f(n) (i.e. there are at least two single, real, non-zero roots of G_{n}(t) greater than r_{1}^{(n)}). Again, there is at least one root of G_{n+1}(t) in (r_{1}^{(n)}, r_{c(n)+1}^{(n)}) (if f(n + 1) = f(n) + 1 and c(n + 1) = c(n)) and in (r_{f(n)−d(n)}^{(n)}, 0) (if d(n + 1) = d(n)), plus at least one root in each of the intervals (r_{c(n)+1}^{(n)}, r_{c(n)+2}^{(n)}), …, (r_{f(n)−d(n)−1}^{(n)}, r_{f(n)−d(n)}^{(n)}) (from Lemma 2.2(i), as b_{k}(t) < 0 for r_{1}^{(n)} < t < 0). Adding the c(n + 1) roots at r_{1}^{(n)} and d(n + 1) roots at 0, we have accounted for at least I_{(f(n+1)=f(n)+1,c(n+1)=c(n))} + I_{(d(n+1)=d(n))} + f(n) − d(n) − c(n) − 1 + c(n + 1) + d(n + 1) roots of G_{n+1}(t). This can be rewritten as f(n) − 1 + I_{(f(n+1)=f(n)+1,c(n+1)=c(n))} + (d(n + 1) − d(n) + I_{(d(n+1)=d(n))})+(c(n + 1) − c(n)), which has a lower bound of f(n)+ I_{(f(n+1)=f(n)+1,c(n+1)=c(n))} (as d(n + 1) − d(n) = 0 or 1), as above.

(II): Suppose that 1 < q < f(n) − d(n) − c(n) + 1 (i.e. there is at least one single, real, non-zero root of G_{n}(t) less than, and greater than, r_{q}^{(n)}).

Firstly, suppose that q = 2 and q+c(n) = f(n)−d(n), which gives c(n)+d(n)+2 = f(n) (i.e. there is exactly one single, real, non-zero root of G_{n}(t) less than, and another such greater than, r_{q}^{(n)} - these are r_{1}^{(n)} and r_{c(k)+2}^{(k)} respectively). There is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}) (if f(n + 1) = f(n) + 1, from Lemma 2.2(ii), as q ≠ 1) and in (r_{2+c(n)}^{(n)}, 0) (if d(n + 1) = d(n), from Lemma 2.2(vi), as r_{f(n)−d(n)}^{(n)} = r_{2+c(n)}^{(n)}) and in either (r_{1}^{(n)}, r_{2}^{(n)}) or (r_{2}^{(n)}, r_{2+c(n)}^{(n)}) (if c(n + 1) = c(n), from Lemma 2.2(v), as q = 2). Adding the c(n + 1) roots at r_{q}^{(n)} (from (A)) and the d(n + 1) roots at 0 we have I_{(f(n+1)=f(n)+1)} + I_{(d(n+1)=d(n))} + I_{(c(n+1)=c(n))} + c(n + 1) + d(n + 1) roots. This can be rewritten as I_{(f(n+1)=f(n)+1)} + d(n) + c(n) + (c(n + 1) − c(n) + I_{(c(n+1)=c(n))}) + (d(n + 1) − d(n) + I_{(d(n+1)=d(n))}), which has a lower bound of I_{(f(n+1)=f(n)+1)}+f(n) (as c(n + 1) ≥ c(n) and d(n + 1) ≥ d(n) and c(n) + d(n) + 2 = f(n)), so f(n + 1) ≥ f(n).

Secondly, suppose that q = 2 and q+c(n) < f(n)−d(n), which gives c(n)+d(n)+2 < f(n) (i.e. there is exactly one single, real, non-zero root of G_{n}(t) less than, and more than one root, each single, greater than, r_{q}^{(n)}). Again, there is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}) (if f(n + 1) = f(n) + 1) and in (r_{f(n)−d(n)}^{(n)}, 0) (if d(n + 1) = d(n)) and in either (r_{1}^{(n)}, r_{2}^{(n)}) or (r_{2}^{(n)}, r_{2+c(n)}^{(n)}) (if c(n + 1) = c(n)), plus roots in the intervals (r_{2+c(n)}^{(n)}, r_{2+c(n)+1}^{(n)}), …, (r_{f(n)−d(n)−1}^{(n)}, r_{f(n)−d(n)}^{(n)}) (from Lemma 2.2(i), as b_{k}(t) < 0 for t < 0 ∩ t ≠ r_{q}^{(m)}). Adding the c(n + 1) roots at r_{q}^{(n)} and the d(n + 1) roots at 0, we have I_{(f(n+1)=f(n)+1)} + I_{(d(n+1)=d(n))} + I_{(c(n+1)=c(n))} + f(n) − d(n) − c(n) − 2 + c(n + 1) + d(n + 1) roots. This can be rewritten as I_{(f(n+1)=f(n)+1)} + f(n) − 2 + (d(n + 1) − d(n) + I_{(d(n+1)=d(n))})+ (c(n + 1) − c(n) + I_{(c(n+1)=c(n))}), which has a lower bound of I_{(f(n+1)=f(n)+1)} + f(n) (as c(n + 1) ≥ c(n) and d(n + 1) ≥ d(n)), as above.

Thirdly, suppose that q > 2 and q + c(n) = f(n) − d(n), (i.e. there are q − 1 real, single non-zero roots of G_{n}(t) less than, and precisely one r_{q+c(n)}^{(n)} greater than, r_{q}^{(n)}). Again, there is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}) (if f(n + 1) = f(n) + 1) and in (r_{f(n)−d(n)}^{(n)}, 0) (if d(n + 1) = d(n)) and in either (r_{q−1}^{(n)}, r_{q}^{(n)}) or (r_{q}^{(n)}, r_{q+c(n)}^{(n)}) (if c(n + 1) = c(n)) plus roots in the intervals (r_{1}^{(n)}, r_{2}^{(n)}), …, (r_{q−2}^{(n)}, r_{q−1}^{(n)}). Adding the c(n+1) roots at r_{q}^{(n)} and the d(n+1) roots at 0, we have I_{(f(n+1)=f(n)+1)}+I_{(d(n+1)=d(n))}+ I_{(c(n+1)=c(n))}+q−2+c(n+1)+d(n+1) roots. This can be rewritten as I_{(f(n+1)=f(n)+1)}+ q−2+c(n)+d(n)+(c(n + 1) − c(n) + I_{(c(n+1)=c(n))})+(d(n + 1) − d(n) + I_{(d(n+1)=d(n))}), which has a lower bound of I_{(f(n+1)=f(n)+1)}+f(n) (as c(n+1) ≥ c(n) and d(n+1) ≥ d(n) and q + c(n) = f(n) − d(n)), as above.

Finally, suppose that q > 2 and q + c(n) < f(n) − d(n), (i.e. there are q − 1 single, real, non-zero roots of G_{n}(t) less than, and more than one greater than, r_{q}^{(n)}). Again, there are roots in (−∞, r_{1}^{(n)}) (if f(n+1) = f(n)+1) and in (r_{f(n)−d(n)}^{(n)}, 0) (if d(n+1) = d(n)) and in either (r_{q−1}^{(n)}, r_{q}^{(n)}) or (r_{q}^{(n)}, r_{q+c(n)}^{(n)}) (if c(n + 1) = c(n)), plus at least one root in each of the intervals (r_{1}^{(n)}, r_{2}^{(n)}), …, (r_{q−2}^{(n)}, r_{q−1}^{(n)}) and (r_{q+c(n)}^{(n)}, r_{q+c(n)+1}^{(n)}), …, (r_{f(n)−d(n)−1}^{(n)}, r_{f(n)−d(n)}^{(n)}). Adding the c(n + 1) roots at r_{q}^{(n)} (from (A)) and the d(n + 1) roots at 0, we have I_{(f(n+1)=f(n)+1)} + I_{(d(n+1)=d(n))} + I_{(c(n+1)=c(n))} + f(n) − d(n) − c(n) − 2 + c(n + 1) + d(n + 1) roots. This can be rewritten as I_{(f(n+1)=f(n)+1)} + f(n) − 2 + (d(n + 1) − d(n) + I_{(d(n+1)=d(n))})+ (c(n + 1) − c(n) + I_{(c(n+1)=c(n))}), which has a lower bound of I_{(f(n+1)=f(n)+1)} + f(n), (as c(n + 1) ≥ c(n) and d(n + 1) ≥ d(n)), as above.

(III): Suppose that q = f(n) − d(n) − c(n) + 1 (i.e. there are no non-zero roots of G_{n}(t) greater than r_{q}^{(n)}).

Firstly, suppose that q = 2, that is c(n) + d(n) + 1 = f(n) (since q = 2, r_{1}^{(n)} is the only non-zero, single root of G_{n}(t) less than r_{q}^{(n)} = r_{2}^{(n)}). There is at least one root of G_{n+1}(t) in (−∞, r_{1}^{(n)}) (if f(n + 1) = f(n) + 1, from Lemma 2.2(ii)) and in (r_{1}^{(n)}, r_{2}^{(n)}) (if d(n + 1) = d(n) and c(n + 1) = c(n), from Lemma 2.2(vii), as r_{f(n)−d(n)−c(n)}^{(n)} = r_{1}^{(n)}). Adding the c(n + 1) roots at r_{f(n)−d(n)−c(n)+1}^{(n)} and the d(n + 1) roots at 0, we have I_{(f(n+1)=f(n)+1)}+I_{(d(n+1)=d(n),c(n+1)=c(n))}+c(n+1)+d(n+1) roots. This can be rewritten as I_{(f(n+1)=f(n)+1)}+c(n)+d(n)+(c(n + 1) − c(n) + d(n + 1) − d(n) + I_{(d(n+1)=d(n),c(n+1)=c(n))}), which has a lower bound of I_{(f(n+1)=f(n)+1)}+f(n) (as c(n+1) ≥ c(n) and d(n+1) ≥ d(n) and c(n) + d(n) + 1 = f(n)), so f(n + 1) ≥ f(n).

Secondly, suppose that q > 2, that is c(n) + d(n) + 1 < f(n) (since q > 2, there are at least two non-zero, single roots of G_{n}(t) less than r_{q}^{(n)}). Again, there is at least one root of G_{n+1}(t) in the intervals in (−∞, r_{1}^{(n)}) (if f(n + 1) = f(n) + 1) and in (r_{f(n)−d(n)−c(n)}, r_{f(n)−d(n)−c(n)+1}) (if d(n + 1) = d(n) and c(n + 1) = c(n)), plus at least one root in each of the intervals (r_{1}^{(n)}, r_{2}^{(n)}), …, (r_{f(n)−d(n)−c(n)−1}^{(n)}, r_{f(n)−d(n)−c(n)}^{(n)}) (from Lemma 2.2(i)). Adding the c(n + 1) roots at r_{f(n)−d(n)−c(n)+1}^{(n)} and the d(n + 1) roots at 0, we have I_{(f(n+1)=f(n)+1)} + I_{(d(n+1)=d(n),c(n+1)=c(n))} + f(n) − d(n) − c(n) − 1 + c(n + 1) + d(n + 1) roots. This can be rewritten as I_{(f(n+1)=f(n)+1)} + f(n) − 1 + ((c(n + 1) − c(n)) + (d(n + 1) − d(n)) + I_{(d(n+1)=d(n),c(n+1)=c(n))}), as above.

4 Proof of Theorem 1.1

We know that for some m ≥ 1, the f(m) − d(m) non-zero roots of G_{m}(t) are all real, distinct (and negative). Now assume for k ≥ m, that the non-zero roots of G_{k}(t) are all real and distinct and are denoted in ascending order by {r_{i}^{(k)}}, i = 1, 2, …, f(k)−d(k). We must prove that the f(k + 1) − d(k + 1) non-zero roots of G_{k}(t) are all real, distinct (and negative).

From Lemma 2.3 (i), the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)} + I_{(d(k+1)=d(k))} + f(k) − d(k) − 1 + d(k + 1). But f(k + 1) − f(k) = 0 or 1 and d(k + 1) − d(k) = 0 or 1, so clearly we have accounted for the total number of roots of G_{k+1}(t).

Therefore, using the working in Lemma 2.3 (i), the f(k+1)−d(k+1) non-zero roots of G_{k+1}(t) are found within the intervals (r_{1}^{(k)}, r_{2}^{(k)}), (r_{2}^{(k)}, r_{3}^{(k)}) …, (r_{f(k)−d(k)−1}^{(k)}, r_{f(k)−d(k)}^{(k)}) (if d(k) + 1 < f(k)) and (−∞, r_{1}) (if f(k + 1) = f(k) + 1) and (r_{f(k)−d(k)}^{(k)}, 0) (if d(k + 1) = d(k)). These intervals are based on the real, single and negative roots of G_{k}(t) and so the non-zero roots of G_{k+1}(t) roots are all real, single and negative.

5 Proof of Theorem 1.2

We shall now use proof by induction to establish in sequence the 3 parts of Theorem 1.2.

Proof by Induction for (A) We know that that for some m ≥ 1, r_{q}^{(m)} is a multiple real root of G_{m}(t) of order c(m). Now assume that for some k ≥ m, r_{q}^{(m)} is a multiple root of G_{k}(t) of order c(k) ≥ c(m). By Lemma 2.3 (ii), r_{q}^{(m)} is a multiple root of G_{k+1}(t) of order c(k + 1) ≥ c(k).

Proof by Induction for (B1) We know that for some m ≥ 1 the f(m) − d(m) non-zero roots of G_{m}(t) are all real, and single except the smallest root r_{1}^{(m)} which is a multiple root of order c(m). Assume for some k ≥ m, that the f(k) − d(k) non-zero roots of G_{k}(t) are all real, and single except the smallest root r_{1}^{(m)} (which, from (A), is a multiple root of order c(k)).

Denote the f(k) roots of G_{k}(t), in ascending order, by r_{1}^{(m)}, r_{2}^{(k)} …, r_{f(k)}^{(k)}, where

r_{1}^{(m)} = r_{2}^{(k)} = … = r_{c(k)}^{(k)} are the roots at r_{1}^{(m)}

r_{c(k)+1}^{(k)}, …, r_{f(k)−d(k)}^{(k)} are the single roots, if c(k) + d(k) + 1 ≤ f(k), and r_{f(k)−d(k)+1}^{(k)} = r_{f(k)−d(k)+2}^{(k)} = … = r_{f(k)}^{(k)} = 0 are the roots at 0, if d(k) ≥ 1.

Firstly, suppose that c(k) + d(k) = f(k) (that is, there are no single, non-zero real roots of G_{k}(t)). From Lemma 2.3 (ii) I, the number of roots of G_{k+1}(t) is at least c(k + 1) + d(k + 1) + I_{(c(k+1)=c(k),d(k+1)=d(k),f(k+1)=f(k)+1)}. This can be rewritten as c(k)+d(k)+I_{(c(k+1)=c(k),d(k+1)=d(k),f(k+1)=f(k)+1)}+(c(k+1)−c(k))+(d(k+1)−d(k)), which reduces to f(k)+I_{(c(k+1)=c(k),d(k+1)=d(k),f(k+1)=f(k)+1)}+(c(k+1)−c(k))+(d(k+1)−d(k)) (as c(k) + d(k) = f(k)).

Altogether, G_{k+1}(t) has a total of f(k + 1) roots (where f(k + 1) − f(k) = 0 or 1) and c(k + 1) ≥ c(k) (from (A)) and d(k + 1) − d(k) = 0 or 1 from (1) and (2), so we have accounted for all the roots of G_{k+1}(t), and c(k +1) must satisfy c(k +1)−c(k) = 0 or 1 (only 1 if d(k+1) = d(k) and f(k+1) = f(k)+1). Clearly, r_{1}^{(m)} is the smallest root.

Secondly, suppose that c(k)+d(k)+1 = f(k) (i.e. there is one single, real, non-zero root r_{c(k)+1}^{(k)} of G_{k}(t), which is greater than r_{1}^{(m)}). Again from Lemma 2.3 (ii) I, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1,c(k+1)=c(k))}+I_{(d(k+1)=d(k))}+c(k+1)+d(k+ 1), which can be rewritten as I_{(f(k+1)=f(k)+1,c(k+1)=c(k))} +c(k)+d(k)+(c(k +1)−c(k))+ (d(k + 1) − d(k) + I_{(d(k+1)=d(k))}). This reduces to f(k) + I_{(f(k+1)=f(k)+1,c(k+1)=c(k))} + (c(k + 1) − c(k)) (as d(k + 1) − d(k) = 0 or 1, and c(k) + d(k) + 1 = f(k)).

Now c(k + 1) ≥ c(k) (from (A)) and f(k + 1) − f(k) = 0 or 1, so we have accounted for all the roots of G_{k+1}(t) and c(k+1)−c(k) = 0 or 1 (always 0 when f(k+1) = f(k)). Clearly, r_{1}^{(m)} is the smallest root and the non-zero roots, other than r_{1}^{(m)}, are real and single.

Finally, suppose that c(k) + d(k) + 1 < f(k) (i.e. there are at least two single, real, non-zero roots of G_{k}(t) greater than r_{1}^{(m)}). Again, from Lemma 2.3 (ii) I, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1,c(k+1)=c(k))} + I_{(d(k+1)=d(k))} + f(k) − d(k) − c(k) − 1 + c(k + 1) + d(k + 1). This can be rewritten as f(k) − 1 + I_{(f(k+1)=f(k)+1,c(k+1)=c(k))} + (d(k + 1) − d(k) + I_{(d(k+1)=d(k))}) + (c(k + 1) − c(k)), which reduces to f(k) + I_{(f(k+1)=f(k)+1),c(k+1)=c(k))} + (c(k + 1) − c(k)) (as d(k + 1) − d(k) = 0 or 1), as above.

Proof by Induction for (B2) We know that for some m ≥ 1 the f(m) − d(m) non-zero roots of G_{m}(t) are all real, and single except for r_{q}^{(m)}, which is a multiple root of order c(m). Assume for some k ≥ m, that the f(k) − d(k) non-zero roots of G_{k}(t) are all real, and single except for r_{q}^{(m)} (which, from (A), is a multiple root of order c(k)).

(i) Suppose that 1 < q < f(m) − d(m) − c(m) + 1 (i.e. there is at least one single, real, non-zero root of G_{k}(t) less than, and greater than r_{q}^{(m)}).

Denote the f(k) roots of G_{k}(t), in ascending order, by r_{1}^{(k)}, r_{2}^{(k)}, …, r_{f(k)}^{(k)}, where

r_{1}^{(k)}, r_{2}^{(k)}, …, r_{q−1}^{(k)} and r_{q+c(k)}^{(k)}, r_{q+c(k)+1}^{(k)}, …, r_{f(k)−d(k)}^{(k)} are the single roots, r_{q}^{(k)} = r_{q+1}^{(k)} = … = r_{q+c(k)−1}^{(k)} are the roots at r_{q}^{(m)} and r_{f(k)−d(k)+1}^{(k)} = r_{f(k)−d(k)+2}^{(k)} = … = r_{f(k)}^{(k)} = 0 are the roots at 0, if d(k) ≥ 1.

In the sequel, we separate the cases q = 2 and q > 2 for greater clarity (as in Lemma 2.3 I and II), though the proofs are very similar.

Firstly, suppose that q = 2 and q +c(k) = f(k)−d(k), which gives c(k)+d(k)+2 = f(k) (i.e. there is exactly one single, real, non-zero root of G_{k}(t) less than, and another such greater than, r_{q}^{(m)}- these are r_{1}^{(k)} and r_{2+c(k)}^{(k)} respectively). From Lemma 2.3 (ii) II, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)} + I_{(d(k+1)=d(k))} + I_{(c(k+1)=c(k))} + c(k + 1) + d(k + 1), which can be rewritten as I_{(f(k+1)=f(k)+1)} + f(k) − 2 + (c(k + 1) − c(k) + I_{(c(k+1)=c(k))}) + (d(k + 1) − d(k) + I_{(d(k+1)=d(k))}). This reduces to I_{(f(k+1)=f(k)+1)} + f(k) − 1 + (c(k + 1) − c(k) + I_{(c(k+1)=c(k))}) (as d(k + 1) − d(k) = 0 or 1 and c(k) + d(k) + 2 = f(k)).

Now c(k + 1) ≥ c(k), from (A)) and f(k + 1) − f(k) = 0 or 1, so we have accounted for the total f(k + 1) roots of G_{k+1}(t), and c(k + 1) − c(k) = 0 or 1. Clearly, the non-zero roots, other than r_{2}^{(m)}, are real and single.

Secondly, suppose that q = 2 and q+c(k) < f(k)−d(k), which gives c(k)+d(k)+2 < f(k) (i.e. there is exactly one single, real, non-zero root of G_{k}(t) r_{1}^{(k)} less than, and more than one root, each single, greater than, r_{q}^{(m)}). Again, from Lemma 2.3 (ii) II, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)} + I_{(d(k+1)=d(k))} + I_{(c(k+1)=c(k))} + f(k)−d(k)−c(k)−2+c(k+1)+d(k+1). This can be rewritten as I_{(f(k+1)=f(k)+1)}+f(k)− 2 + (d(k + 1) − d(k) + I_{(d(k+1)=d(k))}) + (c(k + 1) − c(k) + I_{(c(k+1)=c(k))}), which reduces to I_{(f(k+1)=f(k)+1)} + f(k) − 1 + (c(k + 1) − c(k) + I_{(c(k+1)=c(k))}) (as d(k + 1) − d(k) = 0 or 1), as above.

Thirdly, suppose that q > 2 and q + c(k) = f(k) − d(k), (i.e. there are q − 1 single, real, non-zero roots of G_{k}(t) less than, and precisely one greater than, r_{q}^{(m)}). Again from Lemma 2.3 (ii) II, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)} + I_{(d(k+1)=d(k))} + I_{(c(k+1)=c(k))} + q − 2 + c(k + 1) + d(k + 1). This can be rewritten as I_{(f(k+1)=f(k)+1)}+q−2+c(k)+d(k)+(c(k + 1) − c(k) + I_{(c(k+1)=c(k))})+(d(k + 1) − d(k)+ I_{(d(k+1)=d(k))}), which reduces to I_{(f(k+1)=f(k)+1)}+f(k)−1+(c(k + 1) − c(k) + I_{(c(k+1)=c(k))}) (as d(k+1)−d(k) = 0 or 1 and q+c(k) = f(k)−d(k)), which is the same result as above.

Finally, suppose that q > 2 and q + c(k) < f(k) − d(k), (i.e. there are q − 1 single, real, non-zero roots of G_{k}(t) less than, and more than one greater than, r_{q}^{(m)}). From Lemma 2.3 (ii) II, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)} + I_{(d(k+1)=d(k))} + I_{(c(k+1)=c(k))} + f(k) − d(k) − c(k) − 2 + c(k + 1) + d(k + 1). This can be rewritten as I_{(f(k+1)=f(k)+1)} + f(k) − 2 + (d(k + 1) − d(k) + I_{(d(k+1)=d(k))}) + (c(k + 1) − c(k) + I_{(c(k+1)=c(k))}), which again reduces to I_{(f(k+1)=f(k)+1)} + f(k) − 1 + (c(k + 1) − c(k) + I_{(c(k+1)=c(k))}), as above.

(ii) Now suppose that q = f(m) − d(m) − c(m) + 1 (i.e. there are no non-zero roots of G_{k}(t) greater than r_{q}^{(m)}).

Denote the f(k) roots of G_{k}(t), in ascending order, by r_{1}^{(k)}, r_{2}^{(k)}, …, r_{f(k)}^{(k)}, where

r_{1}^{(k)}, r_{2}^{(k)}, …, r_{f(k)−d(k)−c(k)}^{(k)} are the single roots (< r_{q}^{(m)}),

r_{f(k)−d(k)−c(k)+1}^{(k)} = … = r_{f(k)−d(k)}^{(k)} are the roots at r_{q}^{(m)} and

r_{f(k)−d(k)+1}^{(k)} = r_{f(k)−d(k)+2}^{(k)} = … = r_{f(k)}^{(k)} = 0 are the roots at 0, if d(k) ≥ 1.

Firstly, suppose that q = 2, that is c(k)+d(k)+1 = f(k) (since q = 2, r_{1}^{(k)} is the only non-zero, single root of G_{k}(t) less than r_{q}^{(m)} = r_{2}^{(k)}). From Lemma 2.3 (ii) III, the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)}+I_{(d(k+1)=d(k),c(k+1)=c(k))}+c(k+1)+d(k+ 1). This can be rewritten as I_{(f(k+1)=f(k)+1)}+c(k)+d(k)+(c(k + 1) − c(k) + d(k + 1) − d(k)+ I_{(d(k+1)=d(k),c(k+1)=c(k))}), which reduces to I_{(f(k+1)=f(k)+1)} +f(k)−1+(c(k + 1) − c(k)+ d(k + 1) − d(k) + I_{(d(k+1)=d(k),c(k+1)=c(k))}) (as c(k) + d(k) + 1 = f(k)).

But c(k +1) ≥ c(k) (from (A)) and d(k +1)−d(k) = 0 or 1 and f(k +1)−f(k) = 0 or 1, so we have accounted for the total f(k+1) roots of G_{k+1}(t), and c(k+1)−c(k) = 0 or 1 (only 1 if d(k + 1) = d(k) and f(k + 1) = f(k) + 1).

Secondly, suppose that q > 2, that is c(k) + d(k) + 1 < f(k) (since q > 2, there are at least two non-zero, single roots of G_{k}(t) less than r_{q}^{(m)}). Again from Lemma 2.3 (ii) III,the number of roots of G_{k+1}(t) is at least I_{(f(k+1)=f(k)+1)} + I_{(d(k+1)=d(k),c(k+1)=c(k))} + f(k) − d(k) − c(k) − 1 + c(k + 1) + d(k + 1). This can be rewritten as I_{(f(k+1)=f(k)+1)} + f(k) − 1 + ((c(k + 1) − c(k)) + (d(k + 1) − d(k))+ I_{(d(k+1)=d(k),c(k+1)=c(k))}), as above.

Bibliography

Frobenius, G. (1910) Über die BERNOULLI’schen Zahlen und die EULERschen Polynome. Sitzungsberichte der Preuβischen Akademie der Wissenschaften, pp829-830. Harper, L.H. (1967) Stirling behaviour is asymptotically normal. Ann. Math. Statist. 38, 410-414. Warren, Di (1997) The Frobenius-Harper technique in a general recurrence model. (Positively reviewed for the Applied Probability journals.)