Accepted simple approach for this problem

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*

Another accepted simple approach

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.