11
$\begingroup$

I am looking for a closed form (ideally expressed as elementary functions) of the function $\exp_n(x) = \sum_{k=0}^n x^k / k!$. I am already aware of expressing it in terms of the gamma function.

Background / Motivation

When counting combinations of objects with generating functions, it is useful to be able to express the partial sum $1 + x + \cdots + x^n$ as $\frac{1-x^{n+1}}{1-x}$. For example, to count the number of ways to pick 5 marbles from a bag of blue, red, and green marbles where we pick at most 3 blue marbles and at most 2 red marbles, we can consider the generating function $f(x) = (1+x+x^2+x^3)(1+x+x^2)(1+x+x^2+\cdots)$.

By using the partial sum identity, we can express it as $f(x) = \left(\frac{1-x^4}{1-x}\right)\left(\frac{1-x^3}{1-x}\right)\left(\frac{1}{1-x}\right)$. Simplify, express as simpler product of series, and find the coefficient of the $x^5$ term.

I want to be able to do the same for a generating function in the form $g(x) = \exp_{n_1}(x)^{p_1} \exp_{n_2}(x)^{p_2} \cdots \exp_{n_j}(x)^{p_j}$

The easiest way to extract the coefficient of a given term $x^p / p!$ would be to use a similar closed form expression for $\exp_n(x)$ and a similar technique to $f$.

Attempted Solutions

Differential equation

Recall that the way to prove the identity $1+x+x^2+\cdots+x^n = \frac{1-x^{n+1}}{1-x}$ is to define $S = 1 + x + x^2 + \cdots + x^n$ and notice that: $S - Sx = 1 - x^{n+1}$. Likewise, notice that $y(x) = \exp_n(x)$ satisfies $y - y' = x^n/n!$. Via SAGE, the solution is $y(x) = \frac{c+\Gamma(n+1,x)}{n!}e^x$. Our initial condition $y(0) = 0$ so $c=0$. By (2), $\Gamma(n+1,x) = n! e^{-x} \exp_n(x)$ so we have $y(x) = \exp_n(x)$.

Recurrence Relation

Notice that $\exp_n(x) = \exp_{n-1}(x) + x^n/n!$. Using the unilateral Z-Transform and related properties, we find that $\mathcal{Z}[\exp_n(x)] = (z e^{x/z})/(z-1)$.

Therefore, $\exp_n(x) = \mathcal{Z}^{-1}\left[(z e^{x/z})/(z-1)\right] = \frac{1}{2 \pi i} \oint_C z^n e^{x/z}/(z-1)\;dz$.

$(z^n e^{x/z})/(z-1)$ has two singularities: $z = 1$ and $z = 0$. The point $z = 1$ is a pole of order one with residue $e^x$. To find the residue at $z = 0$ consider the product $z^n e^{x/z} (-1/(1-z)) = -z^n \left( \sum_{m=0}^\infty x^m z^{-m} / m! \right) \left( \sum_{j=0}^\infty x^j \right)$. The coefficient of the $z^{-1}$ term is given when $n - m + j = -1$. The residue of the point $z=0$ is then $-\sum_{m,j} x^m / m! = -\sum_{m=n+1}^\infty x^m / m!$.

Let $C$ by the positively oriented unit circle centered at the origin. By Cauchy's Residue Theorem, $\frac{1}{2 \pi i} \oint_C z^n e^{x/z}/(z-1)\;dz = \frac{1}{2 \pi i} 2 \pi i \left(e^x - \sum_{m=n+1}^\infty x^m / m!\right) = \exp_n(x)$.

Finite Calculus

I've tried to evaluate the sum using finite calculus, but can't seem to make much progress.

  • 14
    It's already an elementary function: you can't get any more elementary than a polynomial.2010-07-31
  • 0
    Well that's true. I'm looking to something analogous to 1 + x + ... + x^n = (1-x^(n+1))/(1-x). Whatever that would be called.2010-07-31
  • 2
    I don't think that's likely. For one thing, the roots of exp_n are much more complicated.2010-07-31
  • 3
    @Qiaochu: would not "closed form" imply an absence of summation symbols? While each instance is a polynomial, he is asking for an expression for the family of such polynomials, which is closed form as a function of n.2010-07-31
  • 0
    Fair enough. Let me make the following suggestion: the factorization you give basically reflects the fact that the products you're interested in can be evaluated by pretending that all of the factors are 1/(1 - x) and then using inclusion-exclusion. The analogous construction in the egf case is probably the best you're going to get.2010-07-31
  • 0
    @Niel: My understanding of "closed-form" is that there are no *infinite* sums (and no recursion, and no "calculus stuff" - limits/derivatives/integrals), using only elementary functions.2010-08-01
  • 0
    @BlueRaja: At the risk of making this a 'discussion' on a medium not meant for it, I'd say I'm surprised by the generousness of your definition; I would not interpret [\sum_{x=1}^n x] to be a closed form expression in both x and n (although that example could easily be put into closed form). To me, summation without a constant upper bound falls under the "recursive function" heading you describe. (Perhaps a case could be made for excepting that for the same reasons as excepting addition/multiplication/exponentiation as recursive functions, but I would rather restrict to those.) [Edits; sorry.]2010-08-01
  • 0
    @Qiaochu: could you elaborate on what you mean regarding "can be evaluated by pretending that all of the factors are 1/(1 - x) and then using inclusion-exclusion"? Thanks.2010-08-02
  • 0
    In your function f(x), first ignore the numerator, then expand the numerator and treat it as an inclusion-exclusion.2010-08-02
  • 0
    Minor nitpick: your index variable in the very first expression is "k", yet the variable and the factorial depend on n. :)2010-08-06
  • 0
    To embed the solution into a more general context you can equate DLMF 8.4.7 and 8.5.1 to express e_n(x) in terms of Confluent Hypergeometric functions and some other terms. Not elementary but well studied.2016-02-28

1 Answers 1