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!