Spivak Prologue, Chapter 2, problem 7: prove $\sum_{i=1}^n k^p$ can always be written as sum of powers of n

Question

This is problem 7 of Spivak's Calculus, 4th Edition, Prologue Chapter 2:

Show that $$\sum_{i=1}^n k^p$$ can always be written in the form $$\frac{n^{p+1}}{p+1} + An^{p} + Bn^{p-1} + Cn^{p-2} + ...$$

There is also a hint to use the method from problem 6.

I have a few questions on some specific details about the solution in the solution book, which I reproduce in what follows:

Let A be the set of all natural numbers for which $$\sum_{i=1}^n k^p$$ can be written in the form $$\frac{n^{p+1}}{p+1} + An^{p} + Bn^{p-1} + Cn^{p-2} + ...$$.

Using induction on $p$, for $p=1$ we have

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

so $p=1$ is in $A$.

Suppose the statement is true for all natural numbers smaller than $p$ (actually the solution book has smaller than or equals; so here is the first question: is it $<$ or $\leq$ here?).

The Binomial Theorem yields: $$(k+1)^{p+1}-k^{p+1} = (p+1)k^p + terms\ involving \sum_{k=1}^n k^r for\ r < p\tag{1}$$

By our induction assumption, we can write each $\sum_{k=1}^n k^r$ as an expression involving powers $n^s$ with $s\leq p$.

Writing out $(1)$ for $k=1,...,n$ we obtain: $$2^{p+1}-1^{p+1}=(p+1)1^p +\ ...$$ $$3^{p+1}-2^{p+1}=(p+1)2^p +\ ...$$ $$(...)$$ $$(n+1)^{p+1}-n^{p+1}=(p+1)n^p +\ ...$$

Adding the equations, we obtain:

$$(n+1)^{p+1} - 1 = (p+1)\sum_{k=1}^n k^p +\ terms\ involving\ \sum_{k=1}^n k^r,\ for\ r<p\tag{2}$$

Now at this point, the solution actually says we obtain something else: $$\frac{(n+1)^{p+1}}{p+1}=\sum_{k=1}^n k^p+\ terms\ involving\ \sum_{k=1}^n k^r,\ for\ r<p\tag{3}$$

So the second question is: what assumptions are involved in obtaining $(3)$? Ie, in (2) does the term 1 on the lefthand side cancel with one of the terms on the righthand side? It is also true that each term on the righthand side has a (p+1) term, so is that term the one dividing the lefthand side?

Finally, as we noted above, because of the induction assumption for all natural numbers less than $p$, we can write each $\sum_{k=1}^n k^r$ as an expression involving powers of $n^s$ with $s\leq p$. Therefore, isolating $\sum_{k=1}^n k^p$ we get: $$\sum_{k=1}^n k^p = \frac{(n+1)^{p+1}}{p+1}+\ terms\ involving\ powers\ of\ n\ less\ than\ p+1$$.

Therefore, if $s$ is in $A$ for $s<p$ then $p$ is in $A$; therefore by induction $A=N$.

Final question: is this considered a rigorous proof?

Answer 1

I think Spivak has just been a little lax, probably intentionally since it was not his point of focus. If we go a little more precisely into things, we can be far more direct : we can get $A,B,C$ etc.

---

Indeed, fix $n$ and $N$ positive integers. We have by the binomial formula: $$ (N+1)^{n+1} = \binom{n+1}{0}N^0 + \binom{n+1}{1} N^{1} + \ldots + \binom{n+1}{n}_{(=n+1)} N^{n} + \binom{n+1}{n+1}_{(=1)} N^{n+1} \\ \implies (N+1)^{n+1} - N^{n+1} = \binom{n+1}{0}N^0 + \binom{n+1}{1} N^{1} + \ldots +(n+1) N^{n} \\ \implies \frac{(N+1)^{n+1} -N^{n+1}}{n+1} = \frac{\binom{n+1}{0}}{n+1}N^0 + \frac{\binom{n+1}{1}}{n+1} N^1 + ... + N^n \\ \implies N^n = \frac{(N+1)^{n+1} -N^{n+1}}{n+1} -\frac{\binom{n+1}{0}}{n+1}N^0 - \frac{\binom{n+1}{1}}{n+1} N^1 - \cdots - \frac{\binom{n+1}{n-1}}{n+1} N^{n-1} $$

and now when we sum from $N=0$ to $K$, the first term on the right has telescoping cancellations and the rest sum up . The following emerges : $$ \sum_{N=0}^K N^n = \frac{(K+1)^{n+1}}{n+1} - \frac 1{n+1} - \frac{\binom{n+1}{0}}{n+1}\sum_{N=0}^K N^0 - \frac{\binom{n+1}{1}}{n+1} \sum_{n=0}^K N^1 - \cdots - \frac{\binom{n+1}{n-1}}{n+1} \sum_{n=0}^K N^{n-1} $$

which provides the exact relation between the sums in question, the super-rigorous and exact proof. This can be used to calculate the first few sum formulas as well, and also provides intuition for why the Bernoulli numbers come into the general formula, from their recurrence relation. You can see here for more details.

---

Of course, note that Spivak did not want to mention all this because he felt that writing out the details was not his intention there, he just wanted to use induction. If you want a proof that does just that, without giving you an explicit formula, then your formulation will be slightly different , and you will have the following :

For each $n = 1,2,...$ there exist rational numbers $C_{n,0},C_{n,1},...,C_{n,n}$ such that for every $K=1,2,...$ , we have : $$ \sum_{N=0}^K N^n = \frac{(N+1)^{n+1}}{n+1} + C_{n,n}N^n + ... + C_{n,0} $$

and how to prove this? Now go by induction, and $n=1$ is clear, and for induction, assume truth for $1,...,n-1$ and you want to prove the statement for $n$. All you need to do is repeat the above argument , but replace each exact quantity (like the binomial coefficients) except $\binom{n+1}{n}$ and $\binom{n+1}{n+1}$ by saying there exist rational numbers in those places. So for example, you would use binomial theorem to say : there exist rational numbers $r_0,...,r_{n-1}$ such that : $$ (N+1)^{n+1} = r_0N^0 + r_1 N^{1} + \ldots + (n+1)N^{n} + N^{n+1} $$ Then you just have to do the summation, perform the manipulations exactly as done before, and you will land up with the same sum, except with $r_i$ instead of the binomial coefficients, which does it. (super-rigorously, if you like!)

Answer 2

Let $s_p(n)=1^p+2^p+\cdots+ n^p$. We know that $s_1(n) = {1 \over 2} n^2+ q_1(n)$, where $q_1$ is a polynomial with degree $\partial q_1 \le 1$. So suppose we know that $s_r(n) = {1 \over r+1}n^{r+1}+ q_r(n)$, with $\partial q_r \le r$ for $r=1,...,p-1$.

Then $(k+1)^{p+1} - k^{p+1} = \sum_{i=0}^{p} \binom{p+1}{i} k^i = (p+1)k^p + \sum_{i=0}^{p-1} \binom{p+1}{i} k^i $. Rearranging gives $k^p = {1 \over p+1}((k+1)^{p+1} - k^{p+1} - \sum_{i=0}^{p-1} \binom{p+1}{i} k^i )$.

Summing both sides with $\sum_{k=1}^n$ gives $s_{p}(n) = {1 \over p+1}((n+1)^{p+1} - 1 - \sum_{i=0}^{p-1} \binom{p+1}{i} s_i(n) )$ and since $\partial \sum_{i=0}^{p-1} \binom{p+1}{i} s_i \le p-1$, we have the desired result.