$$ s_n(p)=\sum_{k=1}^n k^p $$
Show: For every $q \geq 1$ exist rational numbers $ a_{k,q} , 1 \leq k \leq q-1 $, such that
$$ s_n(q)= \frac 1 {q+1} n^{q+1}+ \frac 1 2 n^q + \sum_{k=1}^{q-1} a_{k,q}n^{q-k} $$
I am afraid I don't have a clue on how to prove that. Induction? Rearranging? Before that task the Pascal Identity was introduced:
$$ \sum_{p=0}^q \binom{q+1}p s_n(p)=(n+1)^{q+1} - 1 $$
But I can't really use that, because $s_n(p)$ refers to p and not to q, doesn't it?
Have you got any ideas on how to prove that?
Prove this is true for $s_n(0)$, which should be easy. Then, given $q$, write $$(q+1)s_n(q)=-\sum_{p=0}^{q-1} \binom{q+1}p s_n(p)+(n+1)^{q+1} - 1$$ There are a few more nontrivial steps to complete from here, but this at least tells you it is a polynomial in $n$.