How to find sum $\sum_{x=1}^K x^n(x-1)^m$ 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.

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.$$
