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.
Best Answer
He tells you to use induction. In my copy, he just says:
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$.