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)

The aim of this note is to present a (possibly) simpler solution than the (combined) solution by Morrison, Carlitz, and Riordan [4, 1, 5].

We introduce the generating function

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

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

G(t) = \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 [3, page 537], which is called kernel method by some french authors. It leads to

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

Date: March 24, 2001.

1991 Mathematics Subject Classification. Primary: 05A15.

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

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 [6] 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) is fully explicit:

G(t) = \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 [1] 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 [5] 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 [2] 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}.

Plugging Riordan’s formula into the defining relation (4) we get (setting w = \frac{β−x}{β−α})

g_{n}(x) = β^{n} + ∑_{k=1}^{n−1} A_{k}^{(n)}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} + ∑_{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} + ∑_{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} + [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}}

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

This form was not observed before^{1}. It reminds one of the Lagrange inversion formula! Consequently (see e. g. [7, 8] for the Lagrange inversion formula)

g_{n}(x) = [t^{n}]\frac{1}{1 − y} , where y = tΦ(y), with Φ(y) = \frac{(α − β)yw + β}{1 − yw} . (5)

This can be made explicit, since

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

1Maple V. 4 computed the inner sum in the third line incorrectly, which cost me several hours!

Although in general, (5) holds only for n ≥ 1, it is valid here for n = 0 as well. Therefore we get the generating function

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

This matches with the previous expression for G(t) in (3). Reading all the steps of this section backwards, we obtain a proof of Riordan’s result, purely by the use of generating functions, avoiding any recursions and any guesswork (as in [5]).

References

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

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

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

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

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

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

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

[8] 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 .