The Gift Exchange Problem, Part II

By Moa Apagodu, David Applegate, Neil Sloane, and Doron Zeilberger

So far we had a k-free (partial) recurrence for E_{σ}(n, k) (for σ = 2, 3) (that implied recurrences for G_{σ}(n)) and the trivial n-free (partial) recurrence, (5), for the general E_{σ}(n, k), It turns out that E_{σ}(n, k) satisfies a pure (ordinary) recurrence in k, and that G_{σ}(n) satisfies a linear recurrence with polynomial coefficients, in n, for every σ.

Indeed: we have

∑_{k} E_{σ}(n, k)\frac{y^{k}}{k!} = \frac{1}{n!} (∑_{i=0}^{σ+1} \frac{y^{i}}{i!} )^{n}

Using the J.C.P.Miller ([Z1]) method we get the pure recurrence that enables us, for a given n, to compute fast the numbers E_{σ}(n, k) for a fixed n, without having to use the E_{σ}(n − 1, k)’s

∑_{i=0}^{σ} (\frac{n}{i!} − \frac{k}{(i + 1)!} + \frac{1}{(i − 1)! + i!}) E_{σ}(n, k − i) = 0 .

We also have, using Euler’s integral representation for the factorial

k! = ∫_{0}^{∞} e^{−y}y^{k} dy ,

that we have the integral representation

G_{σ}(n) = \frac{1}{n!} ∫_{0}^{∞} e^{−y} (∑_{i=0}^{σ+1} \frac{y^{i}}{i!} )^{n} dy.

It follows from the (discrete) Almkvist-Zeilberger algorithm [AlZ] that G_{σ}(n) satisfies some homogeneous linear recurrence with polynomial (in n) coefficients , and it follows from Theorem AZ of [ApZ] that its order is σ + 1. The Maple package DavidNeil accompanying this article can easily compute these recurrences, and the the recurrences for 1 ≤ σ ≤ 6, together with the implied asymptotics (using the Poincare-Birkhoff-Trijinksi method as exposited in [WiZ] and implemented in [Z2]) can be found in:

http://www.math.rutgers.edu/~ zeilberg/tokhniot/oDavidNeil1 .

Regarding the generating function

g_{σ}(x) := ∑_{n=0}^{∞} G_{σ}(n)x^{n},

We have,

g_{σ}(x) = ∫_{0}^{∞} exp(x (−y + ∑_{i=0}^{σ+1} \frac{y^{i}}{i!} )) dy.

it follows from the (continuous) Almkvist-Zeilberger algorithm [AlZ] that g_{σ}(x) satisfies some homogeneous linear differential equation with polynomial (in x) coefficients , and it follows from the obvious analog of Theorem AZ of [ApZ] that its order is σ + 1. See

http://www.math.rutgers.edu/~zeilberg/tokhniot/oDavidNeil2

for the differential equations for 1 ≤ σ ≤ 6. These differential equations transcribe to linear recurrences in G_{σ}(n), that are not minimal-order, and for small σ coincide with the ones obtained above using Sister Celine’s technique. Additional References

[AlZ] G. Almkvist and D. Zeilberger, The method of differentiating under the integral sign, J. Symbolic Computation 10 (1990), 571-591.

[ApZ] Moa Apagodu and Doron Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Adv. Appl. Math. 37(2006), 139-152.

[WiZ] Jet Wimp and Doron Zeilberger, Resurrecting the asymptotics of linear recurrences, J. Math. Anal. Appl. 111(1985), 162-177.

[Z1] Doron Zeilbeger The J.C.P. Miller Recurrence for exponentiating a polynomial, and its q-Analog, J. Difference Eqs. and Appls. 1(1995), 57-60.

[Z2] Doron Zeilbeger, AsyRec: A Maple package for Computing the Asymptotics of Solutions of Linear Recurrence Equations with Polynomial Coefficients, The Personal Journal of Ekhad and

Zeilberger, http://www.math.rutgers.edu/ zeilberg/pj.html