# Sum of products of exponentials and polynomials

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!

• For fixed $k$, you can express $n^k$ as a sum of falling factorials, using Sterling numbers. Then you can use partial summation much that you would use integration by parts, to get your closed forms. – David Feldman Nov 22 '11 at 6:29

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$$.

• Great, that was exactly what I needed, and it even taught me some useful tricks. :-) Thanks a lot! – Gregory Crosswhite Nov 22 '11 at 22:15

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...

(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.