Sum of products of exponentials and polynomials

Question

Hi,

I am looking for a closed-form expression for the finite sum of the product of an exponential function with a polynomial function --- that is, the sum

   N
   ∑  a^n * n^k
  n=0

where N and k (but not a) are non-negative integers.

Now, for my problem I don't necessarily need the exact answer as long as I can know that it is always an exponential polynomial (i.e., a product of polynomial and exponential functions). I can see that this is true for the values of k=0...3 (thanks to Wolfram Alpha), but I can't see enough in the pattern to make a good guess at the general answer.

If I ask Wolfram Alpha to calculate the above sum then it gives me:

sum_(n=0)^N a^n n^k = Li_(-k)(a)-a^(N+1) Phi(a, -k, N+1)

where Li is the "polylogarithmic" function and Phi is the "Lerch transcendental function", but this not very helpful because I am not interested in the full analytic case where k could be an arbitrary real or complex number but rather the case where it is a non-negative integer. It is hard for me to see from the above whether for integer values of k it reduces to an exponential polynomial.

So in short, does anyone where I could find a useful closed form for the sum above, or at least where I could find out whether the sum results in an exponential polynomial?

Thanks!

Answer 1

Let $S(N,a,k)= \sum_{n=0}^N a^n n^k$. Multiplying by $x^k/k!$ and summing on $k$ gives the exponential generating function $$\sum_{k=0}^\infty S(N,a,k) \frac{x^k}{k!}= \frac{(ae^x)^{N+1}-1}{ae^x-1}.$$ From this formula, it is easy to calculate $S(N,a,k)$ for small values of $k$ using Maple, Mathematica, or Sage, etc. For $a=1$, we have the well known expression for $S(N,a,k)$ as a polynomial in $N$ in terms of Bernoulli numbers. Now suppose that $a\ne 1$. Then $S(N,a,k) = T(N,a,k) - U(a,k),$ where $$\sum_{k=0}^\infty T(N,a,k) \frac{x^k}{k!}= \frac{(ae^x)^{N+1}}{ae^x-1}$$ and $$\sum_{k=0}^\infty U(a,k) \frac{x^k}{k!}= \frac{1}{ae^x-1}.$$ From the first formula it is not hard to show that $$T(N,a,k)=\frac{a^{N+1}}{(a-1)^{k+1}} Q_k(N,a)$$ where $Q_k(N,a)$ is a polynomial in $N$ and $a$. Using the well-known formula ${1}/(1-ae^x)= \sum_{k=0}^\infty A_k(a)/(1-a)^{k+1}$, where $A_k(a)$ is an Eulerian polynomial, we see that $U(a,k)=(-1)^{k} A_k(a)/(a-1)^{k+1}$. The coefficients of powers of $N$ in $Q_k(N,a)$ can also be expressed explicitly in terms of Eulerian polynomials in $a$.

Answer 2

You really can't do better than the polylogarithm and Lerch's transcendent as closed forms.

For what it's worth, there are the explicit representations

$$\begin{align*}\mathrm{Li}_{-n}(z)&=\frac1{(1-z)^{n+1}} \sum_{m=1}^n \left(\sum_{k=1}^m (-1)^{k+1} \binom{n+1}{k-1}(m-k+1)^n\right)z^m\\\Phi(z,-n,a)&=a^n+\sum_{j=0}^n \binom{n}{j} \mathrm{Li}_{-j}(z) a^{n-j}\end{align*}$$

all valid for $n$ a positive integer. Daunting, no?

If you can't accept these closed forms, then you're better off staying with the sum representation that you have...

Answer 3

(I wanted to comment on Ira Gessel's answer, but can't - therefore as a standalone answer)

Have a look at the excellent and comprehensive article Eulerian Polynomials: from Euler's Time to the Present from Dominique Foata.

In it you can find the explicit formula (page 12, (2.8)) $$\sum_{i=1}^{m}{i^nt^i}=\sum_{l=1}^{n}{(-1)^{n+l}{{n}\choose{l}}\frac{t^{m+1}A_{n-l}(t)}{(t-1)^{n-l+1}}}+(-1)^n\frac{t(t^m-1)}{(t-1)^{n+1}}A_{n}(t)$$ where $A_n$ is the usual Eulerian polynomial.

This formula is in essence what Ira Gessel has described already.