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!



Sum of products of exponentials and polynomials
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$.


