Generalization of sum of powers and arithmetic progression Friend of mine, have found a formula for the summation $\sum \limits_{i=0}^{n-1} (a + d * i )^k$  for given $k,n \in \mathbb{N}$ and $a,d \in \mathbb{R}$.
He checked it for many values, and professor in BGU proved it.
The formula he found is recursive so letting 
$$p(a,d,k,n) = \sum \limits_{i=0}^{n-1} (a + d * i )^k$$ 
the recursive step is on $k$ and he is asking if there is a recursive formula in this form known to the math commuinty ??
In this form :
$$p(a,d,k,n) = f(a,d,k,n)+\sum \limits_{i=0}^{n-1}p(a,d,k-i,n) g(a,d,k,n,i)$$ 
Where $f,g$ are simple function consists of factorials and powers only(which are much simpler than Bernoulli numbers or Stirling numbers).
Any ref to existing formula would be more than helpful.
Thanks.
 A: We have that
$$
\eqalign{
  & p(a,d,k,n) = \sum\limits_{i = 0}^{n - 1} {(a + di)^{\,k} }  = \sum\limits_{i = 0}^{n - 1} {(a + di)(a + di)^{\,k - 1} }  =   \cr 
  &  = a\sum\limits_{i = 0}^{n - 1} {(a + di)^{\,k - 1} }  + d\sum\limits_{i = 0}^{n - 1} {i\;(a + di)^{\,k - 1} }  \cr} 
$$
and applying the Summation by parts
to the second sum, we get
$$
\eqalign{
  & \sum\limits_{i = 0}^{n - 1} {i\;(a + di)^{\,k - 1} }  = \,\left( {n - 1} \right)p(a,d,k - 1,n) + p(a,d,k - 1,0) - \sum\limits_{i = 0}^{n - 1} {p(a,d,k - 1,i)}  =   \cr 
  &  = \,\left( {n - 1} \right)p(a,d,k - 1,n) - \sum\limits_{i = 0}^{n - 1} {p(a,d,k - 1,i)}  \cr} 
$$
i.e.
$$
p(a,d,k,n) = \left( {a + d\left( {n - 1} \right)} \right)\,p(a,d,k - 1,n) - d\sum\limits_{i = 0}^{n - 1} {p(a,d,k - 1,i)} 
$$
Iterating that $k$ times, to reach to $p(a,d,0,n)$, will provide a linear recursion in $p(a,d,k-j,n)$, 
with coefficients that are polynomials in $a,d,n$.
So, sorry to tell that , although not knowing the details, there should be nothing special in your friend's result.
Yet, it is much appreciable if he is fresh in this field.
