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

-