How to find sum $\sum_{x=1}^K x^n(x-1)^m$

Question

I want to find sum of this expression

$\sum_{x=1}^K x^n(x-1)^m$

where $n$ and $m$ are constants around $10^5$ and $K$ is a constant around $10^9$.

So my question is, is there a way to convert this sum in terms of a sum over $m$ and $n$ and not looping over $K$ as it is a very large value?

Actually I want to implement a computer program which tells the value of this sum by taking three inputs $n$, $m$ and $K$. I suspect that it could be reduced in terms of sum over $m,n$ using some binomial coefficients (maybe I am wrong).

Please anybody can help? Thanks in advance.

Answer 1

You can expand $x^n(x-1)^m$ as a polynomial in $x$ by the Binomial Theorem. Then the sums are given by the Faulhaber formulas, accumulating for the different degrees.

---

Alternatively:

The summation on this polynomial of degree $n+m$ gives a polynomial of degree $n+m+1$ in $k$. You can evaluate the sum for $n+m+2$ values of $k$ (e.g. the $n+m+2$ first integers) and form the Lagrangian interpolation polynomial. The coefficients can be found either by straight expansion of the terms (not recommended), by the Neville's algorithm, or by resolution of the linear Vandermonde system.

---

Example:

For $n=m=1$, the sums for $k=0,\cdots3$ are $0,0,2,8$, and the Lagrangian interpolation polynomial is the solution of

$$\begin{pmatrix}1& 0& 0& 0\\1& 1& 1& 1\\1& 2& 4& 8\\1& 3& 9& 27\end{pmatrix}\begin{pmatrix}0\\0\\2\\8\end{pmatrix}=\begin{pmatrix}p_0\\p_1\\p_2\\p_3\end{pmatrix},$$

$$\frac{k^3-k}3.$$

Answer 2

Concerning the asymptotic for large $K$ we have $$ \eqalign{ & S(m,n,K) = \sum\limits_{1\, \le \,x\, \le \,K} {x^{\,n} \left( {x - 1} \right)^{\,m} } = \cr & = K^{\,n + m + 1} \sum\limits_{{1 \over K}\, \le \,{x \over K}\, \le \,1} {\left( {{x \over K}} \right)^{\,n} \left( {{x \over K} - {1 \over K}} \right)^{\,m} {1 \over K}} = \cr & = K^{\,n + m + 1} \sum\limits_{{1 \over K}\, \le \,{x \over K}\, \le \,1} {\left( {\left( {{x \over K} - {1 \over {2K}}} \right) + {1 \over {2K}}} \right)^{\,n} \left( {\left( {{x \over K} - {1 \over {2K}}} \right) - {1 \over {2K}}} \right)^{\,m} {1 \over K}} = \cr & = K^{\,n + m + 1} \sum\limits_{{1 \over {2K}}\, \le \,{y \over K}\, \le \,1 - {1 \over {2K}}} {\left( {{y \over K} + {1 \over {2K}}} \right)^{\,n} \left( {{y \over K} - {1 \over {2K}}} \right)^{\,m} {1 \over K}} = \cr & \approx K^{\,n + m + 1} \sum\limits_{{1 \over {2K}}\, \le \,{y \over K}\, \le \,1 - {1 \over {2K}}} \matrix{ \left( {\left( {{y \over K}} \right)^{\,n} + {n \over {2K}}\left( {{y \over K}} \right)^{\,n - 1} + O\left( {{{n^2 } \over {K^2 }}} \right)} \right) \cdot \hfill \cr \left( {\left( {{y \over K}} \right)^{\,m} + {m \over {2K}}\left( {{y \over K}} \right)^{\,m - 1} + O\left( {{{m^2 } \over {K^2 }}} \right)} \right){1 \over K} \hfill \cr} = \cr & \approx K^{\,n + m + 1} \left( {\int_{x = 0}^1 {x^{\,n + m} dx} \; + {{n + m} \over {2K}}\int_{x = 0}^1 {x^{\,n + m - 1} dx} + {{nm} \over {4K^2 }}\int_{x = 0}^1 {x^{\,n + m - 2} dx} + O\left( {{{nm} \over {K^3 }}} \right)} \right) = \cr & \approx K^{\,n + m + 1} \left( {{1 \over {n + m + 1}}\; + {1 \over {2K}} + {{nm} \over {4\left( {n + m - 1} \right)K^2 }} + O\left( {{{nm} \over {K^3 }}} \right)} \right) \cr} $$ Concerning instead other ways to recast the sum, of course there are many and it is difficult to understand which might better suit your goal, specially when you speak of $K$ being in the order of $10^9$.
Proceeding along the track above, one could be to put the addend as $$ \eqalign{ & {{x^{\,n} \left( {x - 1} \right)^{\,m} } \over {K^{\,n + m} }} = \left( {{x \over K}} \right)^{\,n} \left( {{x \over K} - {1 \over K}} \right)^{\,m} \cr & = \left( {{x \over K} - {1 \over {2K}} + {1 \over {2K}}} \right)^{\,n} \left( {x - {1 \over {2K}} - {1 \over {2K}}} \right)^{\,m} = \cr & = \left( {\xi + {1 \over {2K}}} \right)^{\,n} \left( {\xi - {1 \over {2K}}} \right)^{\,m} = \left( {\xi + {1 \over {2K}}} \right)^{\,{{n + m} \over 2} + {{n - m} \over 2}} \left( {\xi - {1 \over {2K}}} \right)^{\,{{n + m} \over 2} - {{n - m} \over 2}} = \cr & = \left( {\xi ^2 - {1 \over {4K^2 }}} \right)^{\,{{n + m} \over 2}} \left( {{{\xi + {1 \over {2K}}} \over {\xi - {1 \over {2K}}}}} \right)^{\,{{n - m} \over 2}} = \left( {\xi ^2 - {1 \over {4K^2 }}} \right)^{\,{{n + m} \over 2}} \left( {1 + {{{1 \over {K\xi }}} \over {1 - {1 \over {2K\xi }}}}} \right)^{\,{{n - m} \over 2}} \cr} $$ and then, from any point of the above, to develop in series / sum.