Finding a recurrence for a sum I am trying to implement the following sum using a programming language:
$$\sum_{i=1}^N a^i i^r$$
where $N$, $a$ and $r$ are integers.
The problem is, I cannot find a suitable way to do this. Considering $S_r$ as the above sum, I found the following recurrence:
$$S_r=\frac{a^{N+1}(N+1)^r-a\left(1+\displaystyle \sum_{j=0}^{r-1} {r\choose j}S_j\right)}{a-1}$$
But if I use the above recurrence, I cannot evaluate the sum under the given time constraints. So I need to find another recurrence that could help me solve the task but I don't know how to find it. I think that the term:
$$\sum_{j=0}^{r-1} {r\choose j}S_j$$
can be simplified.
To clarify a bit, I am looking for a way to evaluate $S_r$ in $O(r)$ time complexity, the current time complexity is $O(r^2)$.
Any help is appreciated. Thanks!

I sense here the Eulerian numbers and Eulerian Polynomials at work.
Consider the following small GNU Maxima script
display2d : false;

load("simplify_sum");

for r : 1 thru 10 do block(
    h : ratsimp(factor(simplify_sum(sum(a^i*i^r,i,1,n))*(a-1)^(r+1))),
    can : ratcoef(h,a^n),
    print(r,"|",ratexpand(factor((h-can*a^n)/a*(-1)^(r+1))))
);

which writes $S_r$ from above as
$$
S_r = \left[p_r(a,N)\:a^{N+1} + a \: (-1)^{r+1} A_{r-1}(a)\right]/(a-1)^{r+1} 
$$
with p_r(a,N) polynomials of degree $2r$
and $A_{r-1}(a)$ Eulerian polynomials.
See e.g. https://de.wikipedia.org/wiki/Euler-Zahlen
as a reference for the Eulerian polynomials.
Another reference would be http://oeis.org/A008292.
I would first try to evaluate these $A_{r-1}(a)$ in linear time.
