Spivak Chapter 2 Problem 7 Question: Use the method of Problem 6 to show that $\sum_{i=0}^n k^p$ can always be written in the form $\frac{n^{p+1}}{p+1} +An^p + Bn^{p-1} + Bn^{p-2} + Cn^{p-3} + ..... $
The method in 6 they are talking about is the telescoping method.
I have tried to derive the solution for some while and I somewhat came to a proof (there's so much constant terms I am kind of confused).
The solution from the manual is:


I can get a sense of the proof, but I am not quite sure how exactly the part after -- 
"Adding for $k=1,...,n$, we obtain" to the end is exactly formed. An explanation would be very helpful.

Hint: 
If you aren't familiar with the notation, when I write $\mathcal{O}(k^r)$, I basically mean "terms involving $k^r$". Then it should be clear that $\mathcal{O}(k^r) = \frac{1}{p+1} \mathcal{O}(k^r)$. 
In this case, we have $r < p$, so we have
$$(k+1)^{p+1} - k^{p+1} = (p+1)k^p + \mathcal{O}(k^r),$$
so
$$\frac{(k+1)^{p+1} - k^{p+1}}{p+1} = k^p + \frac{\mathcal{O}(k^r)}{p+1} = k^p + \mathcal{O}(k^r),$$ then you can  write
$$
\sum_{k=1}^n k^p + \sum_{k=1}^n \mathcal{O}(k^r)= \sum_{k=1}^n \frac{(k+1)^{p+1} - k^{p+1}}{p+1} = \frac{(n+1)^{p+1}}{p+1} - \frac{1}{p+1},
$$
then you can add $\frac{1}{p+1}$ over to the left side and absorb it into $\mathcal{O}(k^r)$ (since $1 = k^0$).
