Find all pairs $(n,k)$ such that $n(n+1) \, \mid\,(k+1)! \,(1^k+2^k+3^k+\cdots+n^k)$ How can I solve (find all the solutions) the following problem?
Find all pairs of postive integers $(n,k)$ such that
$$n(n+1) \,\mid \,(k+1)!\, (1^k+2^k+3^k+\cdots+n^k).$$
I included here what I had done so far. If $k=1$ and $n=1$, then
$$(k+1)!\cdot (1^k+2^k+\cdots+n^k)=n(n+1)$$ is one solution
Thanks for any help.
 A: It is true for all $n,k \in \mathbb{N}, n,k \geq 1$.
Induction by $k$.
1) For $k=1$ we have $(k+1)! (1^k + \ldots + n^k = 2(1+\ldots+n) = 2 \frac{(n+1)n}{2}=(n+1)n $ , so this is obviously true.
2) For $k \geq 1$ let we assume that that this conditions it true for all previous $j \geq 1, j<k$. 
Cosider following sum:
$\sum_{x=1}^{n}[(x+1)^{k+1}-x^{k+1}] = 2^{k+1}-1^{k+1} +3^{k+1}-2^{k+1}+\ldots + (n+1)^{k+1}-n^{k+1} = (n+1)^{k+1}-1 $.
In other hand $\sum_{x=1}^{n}[(x+1)^{k+1}-x^{k+1}] = \sum_{x=1}^{n} \sum_{j=0}^{k+1}[{ {k+1}\choose j } x^j -x^{k+1}] = 
\sum_{x=1}^{n} \sum_{j=0}^{k}{ {k+1}\choose j } x^j = 
\sum_{j=0}^{k}{ {k+1}\choose j } \sum_{x=1}^{n} x^j 
$
Hence we have:
$   (n+1)^{k+1}-1=  
\sum_{j=0}^{k}{ {k+1}\choose j } \sum_{x=1}^{n} x^j$
$   (n+1)^{k+1}-1=  { {k+1}\choose k } \sum_{x=1}^{n} x^k +
\sum_{j=0}^{k-1}{ {k+1}\choose j } \sum_{x=1}^{n} x^j$
$   (n+1)^{k+1}-1= (k+1) (\sum_{x=1}^{n} x^k) +
\sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j) + n$
Next we multiple both sides of this equality by $k!$  and transforming left side (using formula for $x^n-y^n$):
$   k! ((n+1)-1)((n+1)^{k}+ (n+1)^{k-1}+\ldots+(n+1)^{1}+ 1)= (k+1)! (\sum_{x=1}^{n} x^k) + k!
\sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j) + k! n$
$   k! n((n+1)^{k}+ (n+1)^{k-1}+\ldots+(n+1)^{1}+ 1)= (k+1)! (\sum_{x=1}^{n} x^k) + k!
\sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j) + k! n$
we move $k!n$ to left side end we get:
$   k! n((n+1)^{k}+ (n+1)^{k-1}+\ldots+(n+1)^{1})
= (k+1)! (\sum_{x=1}^{n} x^k) + k! \sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j) + k! n$
We can see that left side of the equality is divisible by $n(n+1)$ and on the right side the sum $k!
\sum_{j=1}^{k-1}{ {k+1}\choose j } (\sum_{x=1}^{n} x^j)$ also is  divisible by $n(n+1)$ , from  assumtion of induction (for $j < k)$.
Hence $ n(n+1) | (k+1)! (\sum_{x=1}^{n} x^k) $, which proves the second step of induction.
