1
$\begingroup$

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: enter image description here enter image description here

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.

$\endgroup$
1
$\begingroup$

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$).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ And what about the terms involving the lower powers of $k$, $k^r$ ($r<p$) in the Right hand side of the equation? Doesn't their co-efficients get divided by $(p+1)$ as well? $\endgroup$ – Rio1210 Mar 22 '17 at 21:03
  • $\begingroup$ I missed that part actually. Let me see if I can fix things. $\endgroup$ – amarney Mar 22 '17 at 21:12
  • $\begingroup$ @amarney: I think that it should be $\dfrac{(n+1)^{p+1}}{p+1}-\dfrac{1}{p+1}$ instead. $\endgroup$ – K.M Jun 27 '19 at 2:33
  • $\begingroup$ yup, forgot that, fixed $\endgroup$ – amarney Jun 28 '19 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.