On Generating Functions Involving the Square Root of a Quadratic Polynomial

David Callan Department of Statistics University of Wisconsin-Madison 1300 University Avenue Madison, WI 53706-1532 USA

                 callan@stat.wisc.edu

Abstract

Many familiar counting sequences, such as the Catalan, Motzkin, Schröder and Delannoy numbers, have a generating function that is algebraic of degree 2. For example, the GF for the central Delannoy numbers is \frac{1}{\sqrt{1−6x+x^{2}}} . Here we determine all generating functions of the form \frac{1}{\sqrt{1+Ax+Bx^{2}}} that yield counting sequences and point out that they have a unified combinatorial interpretation in terms of colored lattice paths. We do likewise for the related forms 1 − \sqrt{1 + Ax + Bx^{2}} and \frac{1+Ax−\sqrt{1+2Ax+Bx^{2}}}{2Cx^{2}} .

1 Introduction

In this paper, all generating functions (GFs) are ordinary power series generating functions. Thus the GF for the formal power series 1 + x + x^{2} + ⋯ is \frac{1}{1−x}. A counting GF is one whose series expansion has nonnegative integer coefficients.

Many familiar counting GFs are algebraic of degree 2 and only involve the square root of a low-degree polynomial. A few such GFs are recalled in Table 1 below, with hyperlinks to the On-Line Encyclopedia of Integer Sequences [1].

Some Algebraic Generating Functions of Degree 2

number sequence (a_{n})_{n≥0}  first few terms GF = ∑_{n≥0} a_{n}x^{n}

even central binomial coefficients 1,2,6,20,70,…

\frac{1}{\sqrt{1−4x}}

odd central binomial coefficients 1,3,10,35,126,…

\frac{1}{2x\sqrt{1−4x}} − \frac{1}{2x}

Catalan numbers 1,1,2,5,14,42,…

\frac{1−\sqrt{1−4x}}{2x}

central trinomial coefficients 1,1,3,7,19,51,…

\frac{1}{\sqrt{1−2x−3x^{2}}}

Motzkin numbers 1,1,2,4,9,21,…

\frac{1−x−\sqrt{1−2x−3x^{2}}}{2x^{2}}

central Delannoy numbers 1,3,13,63,321,…

\frac{1}{\sqrt{1−6x+x^{2}}}

big Schröder numbers 1,2,6,22,90,…

\frac{1−x−\sqrt{1−6x+x^{2}}}{2x}

little Schröder numbers 1,3,11,45,197,…

\frac{1−3x−\sqrt{1−6x+x^{2}}}{4x^{2}}

Table 1

GFs of the form

\frac{1}{\sqrt{1 + Ax + Bx^{2}}}

and

\frac{1 + Ax − \sqrt{1 + 2Ax + Bx^{2}}}{Cx^{2}}

are prominent in Table 1. Our main results, Theorems 1 and 2 below, determine all counting GFs of these two forms and give a unified combinatorial interpretation for them in terms of colored lattice paths. We define and count the relevant lattice paths in §2, and complete the proofs of Theorems 1 and 2 in §3 using basic facts about orthogonal polynomials. Section 4 contains a concluding remark.

The generic unital quadratic polynomial 1+Ax+Bx^{2} can be written as 1−2ax+(a^{2}−4b)x^{2} with a := −A/2 and b := (A^{2} − 4B)/16.

Theorem 1. Set G_{a,b}(x) = \frac{1}{\sqrt{1−2ax+(a^{2}−4b)x^{2}}} . Then

(i ) G_{a,b}(x) = ∑_{n≥0} ( ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}\binom{2k}{k}a^{n−2k}b^{k})x^{n}, (ii ) G_{a,b}(x) is a counting GF ⇔ a, b are nonnegative integers, (iii ) when the conditions in (ii ) hold, G_{a,b}(x) is the GF for a^{H}b^{U}-colored trinomial paths

with x marking the number of steps.

Theorem 1 refers to exponent −1/2 on the quadratic. The situation for exponent +1/2 is a little more subtle. From the identity

1 − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}} = ax + 2b ∑_{n≥0} ( ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}C_{k}a^{n−2k}b^{k})x^{n+2}

(proved below, C_{k} is the Catalan number), it is easy to see that this is a counting GF ⇔ a, b are nonnegative integers (sufficiency is obvious and necessity follows from just the first four coefficients: a, 2b, 2ab, 2a^{2}b + 2b^{2}). But then, also, it is clear that the greatest common divisor of all coefficients from the x^{2} term onward is 2b and so it is natural to consider the refined GF (1 − ax − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}})/(2bx^{2}).

Theorem 2. Set F_{a,b}(x) = (1 − ax − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}})/(2bx^{2}). Then (i ) F_{a,b}(x) = ∑_{n≥0} ( ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}C_{k}a^{n−2k}b^{k})x^{n}, (ii ) F_{a,b}(x) is a counting GF ⇔ a, b are nonnegative integers, (iii ) when the conditions in (ii ) hold, F_{a,b}(x) is the GF for nonnegative a^{H}b^{U}-colored

trinomial paths with x marking the number of steps.

2 GFs for Colored Trinomial Paths

A trinomial path is a lattice path of upsteps U = (1, 1), downsteps D = (1, −1) and horizontal steps H = (1, 0) that starts at the origin and ends on the x-axis. A trinomial n-path is one consisting of n steps. The name derives from the fact that the number of trinomial n-paths is clearly the constant term in (x^{−1} + 1 + x)^{n}, equivalently, the central trinomial coefficient [x^{n}](1 + x + x^{2})^{n}. A nonnegative trinomial path, better known as a Motzkin path, is one that stays weakly above the x-axis. For a, b nonnegative integers, an a^{H}b^{U}-colored trinomial path is one in which each horizontal step is colored with one of a specified colors and each upstep with one of b specified colors. Using Flajolet’s “symbolic” method [2] it is easy to obtain the GF, F (x), for a^{H}b^{U}-colored Motzkin paths with x marking the number of steps: the underlying path is either of the form H^{i} (i ≥ 0) contributing a^{i}x^{i} to the GF, or H^{i}UP DQ (i ≥ 0, P, Q arbitrary Motzkin paths) contributing a^{i}x^{i}bx^{2}H^{2} to the GF. This yields

F (x) = ∑_{i≥0} a^{i}x^{i} + ∑_{i≥0} a^{i}x^{i}bx^{2}F (x)^{2} = \frac{1 + bx^{2}F (x)^{2}}{1 − ax} ,

a quadratic equation for F (x) with (unique) solution

F (x) = \frac{1 − ax − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}}{2bx^{2}} .

The GF, G(x), for a^{H}b^{U}-colored trinomial paths is obtained similarly. The underlying path is (i) empty contributing 1 to the GF, or (ii) F P (P arbitrary trinomial path) contributing axG(x) to the GF, or (iii) UP DQ (P arbitrary Motzkin path, Q arbitrary trinomial path) contributing bx^{2}F (x)G(x) to the GF, or (iv) DP UQ (P arbitrary inverted Motzkin path, Q arbitrary trinomial path) also contributing bx^{2}F (x)G(x) to the GF. This leads to the equation G(x) = 1 + axG(x) + 2bx^{2}F (x)G(x) with solution

G(x) = \frac{1}{\sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}} .

On the other hand, it is also easy to count these colored paths directly by number of upsteps. For Motzkin n-paths containing k upsteps there are \binom{n}{2k} ways to position the slanted steps (U and D) among the n steps. There are C_{k} ways to arrange the slanted steps because they form a Dyck path [3, Ex. 6.19 (i), p. 221]. After applying colors, this yields a total of \binom{n}{2k}C_{k}a^{n−2k}b^{k} choices for a^{H}b^{U}-colored Motzkin n-paths containing k Us. The count for a^{H}b^{U}-colored trinomial n-paths is the same except that C_{k} must be replaced by \binom{2k}{k}.

These results are enough to prove most of both Theorems 1 and 2: part (iii) (of each theorem) and the “sufficiency” half of part (ii) obviously follow. Part (i) also follows because polynomials that agree on the nonnegative integers are identical. Alternatively, one could prove part (i) by setting a = 1 without loss of generality, equating coefficients of x^{n}, and then using the automated WZ method [4] to verify the resulting identities. It remains only to prove “necessity” in part (ii).

3 An application of orthogonal polynomials

The “necessity” half of part (ii) in Theorem 1 says: if p_{n} := ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}\binom{2k}{k}a^{n−2k}b^{k} is a nonnegative integer for all n ≥ 0, then a and b are nonnegative integers. Integrality of a and b follows immediately from the integrality of p_{1} = a and p_{2} = a^{2} + b. Similarly, the nonnegativity of a follows from that of p_{1}, but nonnegativity of b needs that of p_{n} for all n except in the trivial case a = 0. Assuming a > 0, we may without loss of generality set a = 1 and consider the polynomials p_{n}(b) = ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}\binom{2k}{k}b^{k}. Now nonnegativity follows from

Proposition 3. p_{n}(b) ≥ 0 for all n implies b ≥ 0.

Clearly, p_{2}(b) = 1+6b < 0 on (−∞, −1/6) and p_{3}(b) = 1+12b+6b^{2} < 0 on (−1.91 …, −0.08 …), and we claim there exists a sequence of successively overlapping intervals I_{n} that cover (−∞, 0) such that p_{n}(b) < 0 on I_{n}. Proposition 3 follows. The claim in turn follows from the following facts about the zeros of p_{n}.

Proposition 4. Let m denote ⌊n/2⌋ so that deg(p_{n}) = m. Then

(i ) the zeros of p_{n} are real and simple (no repeated roots), say b_{n1} < b_{n2} < ⋯ < b_{nm} < 0 (all zeros are obviously negative),

(ii ) the zeros of p_{n} interlace those of p_{n+1}, that is,

\begin{matrix}b_{n1} < b_{n+1,1} < b_{n2} < b_{n+1,2} < ⋯ < b_{n,n/2} < b_{n+1,n/2} & n even \\ b_{n+1,1} < b_{n1} < b_{n+1,2} < b_{n2} < ⋯ < b_{n+1,(n−1)/2} < b_{n,(n−1)/2} < b_{n+1,(n+1)/2} & n odd, \end{matrix}

(iii ) for fixed integer k ≥ 0, b_{n,m−k} → 0 as n → ∞.

For the claim, use I_{n} = (b_{n,m−1}, b_{nm}) and the case k = 0 of part (iii).

Parts (i) and (ii) of Proposition 4 are reminiscent of orthogonal polynomials and indeed the p_{n} are closely related to the Legendre polynomials P_{n}(x) which are known to form an orthogonal polynomial sequence. Recall that the GF for the Legendre polynomials is

∑_{n≥0} P_{n}(x)w^{n} = \frac{1}{\sqrt{1 − 2xw + w^{2}}}

while the GF for p_{n} is

∑_{n≥0} p_{n}(b)w^{n} = \frac{1}{\sqrt{1 − 2w + (1 − 4b)w^{2}}} .

It follows that P_{n} and p_{n} are related by

P_{n}(x) = x^{n}p_{n}(\frac{x^{2} − 1}{4x^{2}}).  (1)

The well known properties of orthogonal polynomials imply that the zeros of P_{n}(x) are real, simple and possess the interlacing property. Also, P_{n} is alternately even/odd and so its zeros are symmetric about 0. In particular, P_{n} has m := ⌊n/2⌋ positive zeros. If (x_{i})_{i=1}^{m} are the positive zeros of P_{n} in increasing order, then by (1), (\frac{1}{4}(1 − \frac{1}{x_{i}^{2}} ))_{i=1}^{m} are the zeros of p_{n}, also in increasing order. Parts (i) and (ii) of Proposition 4 follow.

Part (iii) is a simple consequence of (1), the fact that cos θ → 0 as θ → π/2, and Bruns’ inequalities for the zeros of the Legendre polynomials, which show that the zeros of P_{n}(cos θ) are fairly evenly spaced around the unit halfcircle. (All zeros of P_{n}(x) lie in the interval (−1, 1), as is evident from (1) ).

Bruns’ Inequalities [5] Let θ_{1} < θ_{2} < ⋯ < θ_{n} denote the zeros of P_{n}(cos θ) in the interval (0, π). Then

\frac{j − \frac{1}{2}}{n + \frac{1}{2}} π < θ_{j} < \frac{j}{n + \frac{1}{2}} π j = 1, 2, …, n.

This completes the proof of Theorem 1.

Similarly, for Theorem 2 we must show that the following result holds for q_{n}(b) := ∑_{k=0}^{⌊n/2⌋} \binom{n}{2k}C_{k}b^{k}.

Proposition 5. q_{n}(b) ≥ 0 for all n implies b ≥ 0.

To prove Prop. 5, we again obtain a sequence of overlapping intervals covering (−∞, 0) on the nth of which q_{n} is negative. Here we find

Q_{n}(x) = (n + 1)x^{n}q_{n}(\frac{x^{2} − 1}{4x^{2}}).  (2)

where the Q_{n}(x) are the Jacobi polynomials J(n, 1, 1, x), which are also orthogonal. (The Legendre polynomial P_{n}(x) is J(n, 0, 0, x).) So, as before, the two largest zeros of q_{n} yield the overlapping intervals. Bruns’ inequalities fail here but since D_{x}(xq_{n}(x)) = p_{n}(x), the zeros of p_{n} separate those of q_{n}, and Prop. 4 (iii) with k = 1 implies that the largest zero of q_{n} tends to 0 as n → ∞ and so the overlapping intervals cover all of (−∞, 0).

This completes the proof of Theorem 2. Table 2 below contains some OEIS sequences whose GFs are of the types considered above. Boldface a, b indicate cases where the quadratic degenerates to a linear polynomial, that is, where a^{2} − 4b = 0.

generalized Motzkin GF  generalized central trinomial GF
a b \frac{1 − ax − \sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}}{2bx^{2}}  \frac{1}{\sqrt{1 − 2ax + (a^{2} − 4b)x^{2}}}

generates this counting series generates this counting series

1 1  Motzkin numbers  central trinomial coefficients

1 2 A025235

central coeff (1 + x + 2x^{2})^{n}
1 3  –  central coeff (1 + x + 3x^{2})^{n}
2 1  shifted Catalan numbers  even central binomial coeffs
2 2  restricted plane trees  restricted Delannoy paths
2 3  –  central coeff (1 + 2x + 3x^{2})^{n}
3 1  restricted hex polyominoes  restricted Delannoy paths
3 2  little Schröder numbers  central Delannoy numbers
3 3  A107264  –
4 1  walks on cubic lattice  central coeff (1 + 4x + x^{2})^{n}

4 2 A068764

transform of central Delannoy

4 3 eigensequence for INVERT colored Delannoy paths 4 4 rooted bipartite planar maps

A059304

4 5  –  A098443
5 4  lattice paths w/steps (k, ±k)  central coeff (1 + 5x + 4x^{2})^{n}
5 5  colored Motzkin paths  –
5 6  –  colored Delannoy paths

6 8 A090442

central coeff (1 + 6x + 8x^{2})^{n}
6 9 A101601 A098658

7 12 A098659

central coeff (1 + 7x + 12x^{2})^{n}
8 16  A098430  –

Table 2

4 Concluding remarks

The middle coefficient of (1 + ay + by^{2})^{n} is the constant term in (y^{−1} + a + by)^{n} and, by counting terms in the expansion, it is easy to see that this is the number of a^{H}b^{U}-colored trinomial n-paths as defined above. By Theorem 1, then, the GF for the middle coefficient of (1 + ay + by^{2})^{n} is (1 − 2ax + (a^{2} − 4b)x^{2})^{− \frac{1}{2}} . Graham, Knuth and Patashnik [6, p. 575] attribute this result to Herbert Wilf, citing his book generatingfunctionology [7] but it does not seem to be there!

References

[1] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences,

    http://www.research.att.com/~njas/sequences/index.html .

[2] Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, 1996.

[3] Richard P. Stanley, Enumerative Combinatorics Vol. 2, Cambridge University Press, 1999. Exercise 6.19 and related material on Catalan numbers are available online at

    http://www-math.mit.edu/~rstan/ec/ .

[4] Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger, A=B, AK Peters, Ltd., 1996. Free

    download available from http://www.cis.upenn.edu/~wilf/AeqB.html .

[5] Gabor Szego, Orthogonal Polynomials, 4th ed., AMS, Providence, RI, 1975.

[6] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics (2nd edition), Addison-Wesley, 1994.

[7] Herbert S. Wilf, generatingfunctionology, Academic Press, New York, 1990. Free down-

    load available from http://www.math.upenn.edu/~wilf/DownldGF.html .

2000 Mathematics Subject Classification: Primary 05A15. Keywords: generating function, colored lattice path.

(Concerned with sequences \underline{A000108}, \underline{A000984}, \underline{A001003}, \underline{A001006}, \underline{A001700}, \underline{A001850}, \underline{A002212}, \underline{A002426}, \underline{A003645}, \underline{A005572}, \underline{A006139}, \underline{A006318}, \underline{A006442}, \underline{A007564}, \underline{A025235}, \underline{A026375}, \underline{A059231}, \underline{A059304}, \underline{A068764}, \underline{A069835}, \underline{A071356}, \underline{A080609}, \underline{A081671}, \underline{A084601}, \underline{A084603}, \underline{A084609}, \underline{A084768}. \underline{A084771}, \underline{A084773}, \underline{A090442}, \underline{A098430}, \underline{A098443}, \underline{A098658}, \underline{A098659}, \underline{A101601}, \underline{A107264}, and \underline{A107265}.)

Received September 24 2006; revised version received May 4 2007. Published in Journal of Integer Sequences, May 7 2007.

Return to Journal of Integer Sequences home page.