# Spivak's Calculus (Chapter 2, Exercise 17)

I am having trouble completing exercise 17 of chapter 2 of Spivak's Calculus. In this exercise, the reader is asked to prove that for all natural numbers $n$ and $p$, there exist real numbers $\alpha_1,\ldots,\alpha_p$ such that: $$\sum_{k = 1}^n k^p ~=~ \frac{n^{p + 1}}{p + 1} + \sum_{i = 1}^p \alpha_in^i$$ The attempted proof of the identity that I devised uses the binomial theorem with $p$ and $n$ fixed, but does not use complete induction. The proof of the identity provided by Spivak uses the binomial theorem with $n$ fixed, but uses complete induction on $p$ to complete the proof. What follows is my attempted proof.

In this proof, I apply $(x + 1)^{y + 1}$ and $(n + 1)^{p + 1}$ to the binomial theorem in order to derive the first and second terms of the sum on the left-hand side of the identity to be proved. First, note that applying $(x + 1)^{y + 1}$ to the binomial theorem, where $x$ is a real number and $y$ a natural number, demonstrates that the predicate $\phi(x,y)$ is true for all real numbers $x$ and natural numbers $y$: $$\phi(x,y) ~\equiv~ (x + 1)^{y + 1} - x^{y + 1} ~=~ (y + 1)x^y + \sum_{i = 0}^{y - 1} {y + 1 \choose i} x^i$$ Now, suppose that $n$ and $p$ are natural numbers. Then the sum of the left-hand sides of the identities $\phi(k,p)$ and the sum of the right-hand sides of the identities $\phi(k,p)$, for $k = 1,\ldots,n$, are equal: $$(n + 1)^{p + 1} - 1 ~=~ \sum_{k = 1}^n (p + 1)k^p + \sum_{k = 1}^n \left ( \sum_{i = 0}^{p - 1} {p + 1 \choose i} k^i \right )$$ Rewriting $(n + 1)^{p + 1}$ using the identity $\phi(n,p)$ and dividing both sides of the identity by $p + 1$ gives $$\sum_{i = 1}^n k^p ~=~ \frac{n^{p + 1}}{p + 1} + \sum_{i = 0}^p {p + 1 \choose i} \left ( \frac{1}{p + 1}\right ) n^i - \left [\frac{1}{p + 1} + \sum_{k = 1}^n \left ( \sum_{i = 0}^{p - 1} {p + 1 \choose i} \frac{k^i}{p + 1} \right ) \right ]$$ Assuming that I didn't make any algebraic errors, I have shown that there are $\alpha_1,\ldots,\alpha_p$ such that the sum of the $p$th powers of the first $n$ natural numbers can be written in the required way. On the other hand, Spivak derives an identity containing the sums of the $r$th powers of the first $n$ natural numbers, for $r \leq p$, then applies an induction hypothesis to obtain the case for $p + 1$. I'm not sure if my proof is wrong, and whether I am missing something that would require a proof by induction. Is there an error?

For reference: I wrote functions that compute the sum of the $p$h power of the first $n$ numbers, and a version of the last identity derived before expanding $(n + 1)^{p + 1}$ using $\phi(n,p)$ in Haskell. Both computed the same numbers for all values of $n \leq 100$ and $p \leq 10$, so for a few numbers there seems to be no problem. Of course, there are more numbers greater than the number of cases that I tested.

-
You really should be using induction. He tells you to use it. – Pedro Tamaroff Aug 18 '12 at 3:22
I tried using complete induction on $p$. However, I found that expanding $(n + 1)^{p + 1}$ using the binomial theorem generated the sum of the $\alpha_i n^i$ that I needed. It's not clear where I should use induction. – danportin Aug 18 '12 at 3:24
I'll try to write something out for you. – Pedro Tamaroff Aug 18 '12 at 3:25

He tells you to use induction. In my copy, he just says:

Use the methods of problem $6$ to prove that $$\sum_{k=0}^n k^p$$ may be written in the form

$$\frac{n^{p+1}}{p+1}+An^{p}+Bn^{p-1}+Cn^p+\dots$$

The really important thing here is

$$\frac{n^{p+1}}{p+1}$$

and later on you'll find out why.

Basically, he hints on using the "recursive" trick to obtaining

$$S_{p+1}$$ from $S_p,\dots,S_1$

where $$S_p=\sum_{k=0}^n k^p$$

Say we want $$S_2=\sum_{k=0}^n k^2$$

Then we note that $$(k+1)^3=3k^2+3k+1$$

So that

$$(k+1)^3-k^3=3k^2+3k+1$$

Now we sum $k=1,\dots,n$.

$$\sum_{k=1}^n(k+1)^3-k^3=3\sum_{k=1}^nk^2+3\sum_{k=1}^nk+\sum_{k=1}^n1$$

$$(n+1)^3-1^3=3\sum_{k=1}^nk^2+3\frac{n(n+1)}{2}+n$$

$$\frac{{{{(n + 1)}^3}}}{3} - \frac{{n + 1}}{2} - \frac{{n(n + 1)}}{2} = \sum\limits_{k = 1}^n {{k^2}}$$

(Expansion aside).

So the idea is that you assume the result true for $p=1,\dots,l$ and prove it for $l+1$. Note you shouldn't be too explicit about the coefficients, and the induction is to be done on $p$, not on $n$.

-
Thank you for responding. I used this method in order to solve the problems in Exercise 6. I attempted to generalize the method to problem 17 by applying the binomial theorem to $(k + 1)^{n + 1}$ in order to obtain an expansion that the method of Exercise 6 requires. What is bothering me is the following: assuming that I didn't make any errors, why did I use the method of Exercise 6 in order to obtain a term of the required form without induction, but Spivak used the method of Exercise 6 to obtain a term of the required for with induction? This leads me to believe that I made an error. – danportin Aug 19 '12 at 6:23
@danportin I'm guessing you didn't make an error, but just over complicated things. =) – Pedro Tamaroff Aug 19 '12 at 17:45