2

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.

Ahmad
  • 1,380
  • 1
  • 18
  • 37

1 Answers1

1

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.

G Cab
  • 35,272