It is easy to solve this problem by using such recursive formula
(k+1)P_k(N)=(N+1)^(k+1)-1-sum_(l=0)^(k-1) C_(k+1)^l P_l(N),
where
P_k(N) is a sum of powers k from 1 up to N,
C_k^l is a binomial coefficient.
I assume that P_0(N)=N.
You can check this formula by summing up from 1 to N following identities
(n+1)^k-n^k=sum_(l=0)^(k-1) C_k^l n^l.

However, P_k(x) has non-integer coefficients, so it is better to introduce polynomials Q_k(x) by formula Q_k(x)=(k+1)!P_k(x). It can be proven by induction based on recursive formula above that Q(x) has integer coefficients!!! So, use BigIntegers in Java, otherwise you would have overflow. Good luck!

Edited by author 08.05.2017 19:44

Edited by author 08.05.2017 19:44

You can make a system of linear equations with k+2 variables and equations, which would look like:
A_0 * 1^0 + A_1 * 1^1 + ... + A_(k+2) * 1^(k+2) = 1^k
A_0 * 2^0 + A_1 * 2^1 + ... + A_(k+2) * 2^(k+2) = 2^k
...
A_0 * (k+2)^0 + A_1 * (k+2)^1 + ... + A_(k+2) * (k+2)^(k+2) = (k+2)^k

So, you only need to find A_i coefficients using Gaussion elimination.