Séminaire Lotharingien de Combinatoire 46 (2001), Article B46a

ON A FUNCTIONAL–DIFFERENCE EQUATION OF RUNYON, MORRISON, CARLITZ, AND RIORDAN

HELMUT PRODINGER

Abstract. A certain functional–difference equation that Runyon encountered when analyzing a queuing system was solved in a combined effort of Morrison, Carlitz, and Riordan. We simplify that analysis by exclusively using generating functions, in particular the kernel method, and the Lagrange inversion formula.

1. The equation

The functional–difference equation in the title is

(x−α)(α−β)^{n−1}g_{n}(x) = α(x−β)^{n}g_{n−1}(α)−x(α−β)^{n}g_{n−1}(x), n ≥ 1, g_{0}(x) = 1. (1)

J. P. Runyon encountered it in a study of a queuing system in which a group of servers handles traffic from two sources, one of which is preferred over the other^{1}.

The aim of this note is to present a (possibly) simpler solution than the (combined) solution by Morrison, Carlitz, and Riordan [6, 2, 7]. Note that the g_{n}(x) are polynomials in x with rational coefficients in α, β. (Our arguments will re-establish that fact.)

We introduce the generating function

G(t, x) := ∑_{n≥0}(α − β)^{n−1}g_{n}(x)t^{n}.

Multiplying (1) by t^{n} and summing we get

(x − α)G(t, x) − \frac{x − α}{α − β} = α(α − β)G(α, \frac{x−β}{α−β} t) − xt(α − β)^{2}G(t, x),

or

G(t, x) = \frac{α ∑_{n≥1}(x − β)^{n}t^{n}g_{n−1}(α) + \frac{x−α}{α−β}}{x − α + xt(α − β)^{2}} .  (2)

Now for

x = x̄ := \frac{α}{1 + t(α − β)^{2}}

the denominator of (2) vanishes. Consequently, the numerator must also vanish. (A more elaborate argument would be that the power series expansion must exist for that combination of values.) This is reminiscent of Knuth’s trick [5, page 537], which is called kernel method by some french authors; see e. g. [1].

1991 Mathematics Subject Classification. Primary: 05A15.

Key words and phrases. functional-difference equation, generating function, Lagrange inversion formula, kernel method.

1This is the only information found in Morrison’s paper; apparently, Runyon was his colleague at Bell Telephone Laboratories and asked him this question. Zentralblatt and Mathematical Reviews don’t give a hint to any publications of Runyon in the open literature.

It leads to

∑_{n≥1}(x̄ − β)^{n}t^{n}g_{n−1}(α) = \frac{x̄ − α}{(β − α)α}.

Now we set T = (x̄ − β)t, i. e.

t = \frac{1 − T (α − β) − \sqrt{1 − 2T (α + β) + T^{2}(α − β)^{2}}}{2β(α − β)} .

So

∑_{n≥0} T^{n}g_{n}(α) = \frac{1 + T (α − β) − \sqrt{1 − 2T (α + β) + T^{2}(α − β)^{2}}}{2T α} .

The expansion of this generating function is well known, from the context of the Narayana (Runyon!) numbers [8] or elsewhere. In any instance, the coefficients could be easily detected by the Lagrange inversion formula, with the result

g_{n}(α) = \frac{1}{n} ∑_{k=0}^{n−1} \binom{n}{k}\binom{n}{k + 1}β^{n−k}α^{k}, n ≥ 1, g_{0}(α) = 1.

In the next section, we will see a more impressive occurrence of the Lagrange inversion formula.

2. The general case

In this section we move from the particular case of g_{n}(α) to the general case of g_{n}(x).

Now that the series in the numerator of (2) is established, the generating function G(t, x) is fully explicit:

G(t, x) = \frac{1 + t(x − β)(α − β) − \sqrt{1 − 2t(x − β)(α + β) + t^{2}(x − β)^{2}(α − β)^{2}} + \frac{2(x−α)}{α−β}}{2(x − α + xt(α − β)^{2})} ,

(3)

and one could work out some clumsy expressions for the coefficients, e. g. (for x ≠ α)

g_{n}(x) = \frac{(α − β)^{n}x^{n}}{(α − x)^{n}} − α ∑_{k=1}^{n} x^{n−k}(α − x)^{k−1−n}(α − β)^{n+1−2k}(x − β)^{k}g_{k−1}(α).

This was obtained by Morrison without using the generating function. Carlitz [2] set

g_{n}(x) = ∑_{k=0}^{n−1} A_{k}^{(n)}(α − β)^{−k}(x − β)^{k}  (4)

and managed to express the coefficients as follows:

A_{r}^{(n)} = βϕ_{r,n−1} − α ∑_{s=1}^{r−1} g_{r−s}(α) ϕ_{s−1,n−r+s−1} − βϕ_{r−1,n−1},

with

ϕ_{r,k} = ∑_{j=0}^{min\{r,k\}} \binom{r}{j}\binom{k}{j}α^{j}β^{k−j}, k ≥ 0, ϕ_{r,k} = 0, k < 0.

He asked whether the expressions

C_{r,n} := ∑_{s=1}^{r−1} g_{r−s}(α) ϕ_{s−1,n−r+s−1}

can be simplified. Now Riordan [7] proved that

A_{k}^{(n)} = (n − k) ∑_{j=1}^{k} \frac{1}{j}\binom{n − 1}{j − 1}\binom{k − 1}{j − 1}α^{j}β^{n−j}, 1 ≤ k < n,

and A_{0}^{(n)} = β^{n}. (This was then generalized by Carlitz [3] who produced a q–version of that.) Riordan’s answer translates as

C_{r,n} = ∑_{j=1}^{min\{r,n\}} \binom{min\{r, n\}}{j}\binom{max\{r, n\} − 1}{j − 1}α^{j−1}β^{n−j}.

We are going to prove Riordan’s result, purely by the use of generating functions and Lagrange’s inversion formula, avoiding any recursions and any guesswork (as in [7]).

We start with the expression for G(t, x) in (3) and write it as

∑_{t≥0} t^{n}g_{n}(x) = \frac{1}{1 − y}

with

y = \frac{α−β+t(β−α)(β−x)−\sqrt{(β−α)^{2}−2(β−α)(α+β)(β−x)t+(β−α)^{2}(β−x)^{2}t^{2}}}{2(x − β)} .

Consequently (see e. g. [9, 10] for the Lagrange inversion formula)

g_{n}(x) = [t^{n}]\frac{1}{1 − y} , where y = tΦ(y),

with Φ(y) = \frac{(α − β)yw + β}{1 − yw} and w = \frac{β − x}{β − α}.

(5)

Hence^{2}

g_{n}(x) = \frac{1}{n}[z^{n−1}]\frac{1}{(1 − z)^{2}} (\frac{(α − β)zw + β}{1 − zw} )^{n}

= β^{n} + [z^{n−1}]\frac{1}{(1 − z)^{2}} \frac{1}{n} ∑_{j=1}^{n} \binom{n}{j}α^{j}β^{n−j} \frac{(zw)^{j}}{(1 − zw)^{j}}

= β^{n} + ∑_{j=1}^{n} \frac{1}{j}\binom{n − 1}{j − 1}α^{j}β^{n−j}[z^{n−1}]\frac{(zw)^{j}}{(1 − z)^{2}(1 − zw)^{j}}

= β^{n} + ∑_{j=1}^{n} \frac{1}{j}\binom{n − 1}{j − 1}α^{j}β^{n−j} ∑_{k=j}^{n}(n − k)\binom{k − 1}{j − 1}w^{k}

= β^{n} + ∑_{k=1}^{n}(n − k) ∑_{j=1}^{k} \frac{1}{j}\binom{n − 1}{j − 1}\binom{k − 1}{j − 1}α^{j}β^{n−j}w^{k}

= β^{n} + ∑_{k=1}^{n−1} A_{k}^{(n)}w^{k}.

Remark. As one referee has pointed out, an early application of the kernel method (but not as early as Knuth’s!) was in queuing models, see [4].

References

[1] C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, D. Gouyou-Beauchamps. Generating Functions of Generating Trees Discrete Mathematics, to appear, 2001.

[2] L. Carlitz. A functional–difference equation. Duke Mathematical Journal, 31:449–453, 1964.

[3] L. Carlitz. Some difference equations. Duke Mathematical Journal, 33:27–31, 1966.

[4] G. Fayolle and R. Iasnogorodski. Solutions of functional equations arising in the analysis of twoserver queueing models. In Performance of computer systems (Proc. Fourth Internat. Sympos. Modelling Performance Evaluation Comput. Systems, Vienna, 1979), pages 289–303. North-Holland, Amsterdam, 1979.

[5] D. E. Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms. Addison-Wesley, 1973. Third edition, 1997.

[6] J. Morrison. A certain functional–difference equation. Duke Mathematical Journal, 31:445–448, 1964.

[7] J. Riordan. A functional–difference equation. Duke Mathematical Journal, 33:23–25, 1966.

[8] J. Riordan. Combinatorial Identities. John Wiley, 1968.

[9] R. Stanley. Enumerative combinatorics. Vol. 2. Cambridge University Press, Cambridge, 1999.

[10] H. S. Wilf. Generatingfunctionology, 2nd Edition. Academic Press, 1994.

Helmut Prodinger, The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa, email: helmut@gauss.cam.wits.ac.za, www–address:

http://www.wits.ac.za/helmut/index.htm .

2This form (first line) of the polynomials g_{n}(x) was not observed before, although it is quite appealing. Maple V. 4 computed the inner sum in the fourth line incorrectly, which cost me several hours!