# Possibility of inductive proof on leading term?

I actually have two questions on the following problem:

It is known that the leading term of the sum $\sum_{i=0}^n i$ is $n^2/2$, and for the $\sum_{i=0}^n i^2$ the leading term is $n^3/3$. Can you make a guess what's the leading term in $\sum_{i=0}^n i^3$? in $\sum_{i=0}^n i^k$? Can you prove something inductively for this?

Clearly the guess is the leading term would be: $n^{k+1}/{(k+1)}$ However, I have two questions here. 1. I don't really understand what this problem means by "leading term". If there are no variables in the sum, how can there be terms? 2. I couldn't find anywhere in my text if an inductive proof applies for just proving a leading term. Does it?

-
But $n$ is a variable. –  André Nicolas Sep 8 '11 at 19:01
The results of those sums are expected to be polynomials in $n$. In that context, the "leading term" of a polynomial is the term that contains the largest power. –  J. M. is back. Sep 8 '11 at 19:04
@Glockstock: Don't erase your question, especially after multiple have already put their time into answering it. I've undone your edit. –  Zev Chonoles Sep 8 '11 at 21:12
Zev - thanks, noted. –  Glockstock Sep 9 '11 at 4:32

In principle you can use induction whenever you’re trying to prove a statement of the form $$P(k)\text{ is true for all integers }k \ge k_0,$$ where $P(k)$ is some assertion about the number $k$. Here the assertion $P(k)$ is a bit complicated: $$\text{for all integers }n\ge 0,\sum_{i=0}^n i^k\text{ is a polynomial in }n\text{ whose leading term is }\frac{n^{k+1}}{k+1}.$$

It is in fact possible to prove this by induction on $k$, though the proof is difficult enough that I’m not at all sure that the question is actually asking you to find it.

Suppose that you know that for every $k<m$, $$\sum_{i=0}^n i^k = \frac{n^{k+1}}{k+1} + p_k(n),$$ where $p_k$ is a polynomial of degree at most $k$. You’d like to use this hypothesis to show that $$\sum_{i=0}^n i^m = \frac{n^{m+1}}{m+1} + p_m(n)$$ for some polynomial $p_m$ of degree at most $m$. The trick is to skip a step and look at $\sum_{i=0}^n i^{m+1}$: \begin{align*} \sum_{i=0}^n i^{m+1} + (n+1)^{m+1} &= \sum_{i=0}^n (i+1)^{m+1}\\ &= \sum_{i=0}^n\left(i^{m+1}+(m+1)i^m + q_{m-1}(i) \right)\\ &= \sum_{i=0}^n i^{m+1} + (m+1)\sum_{i=0}^n i^m + \sum_{i=0}^n q_{m-1}(i), \end{align*} where the second step uses the binomial expansion, and $q_{m-1}$ is a polynomial of degree at most $m-1$ containing the remaining terms of that expansion. Subtracting $\sum_{i=0}^n i^{m+1}$ from both sides, we have $$\qquad\qquad(n+1)^{m+1} = (m+1)\sum_{i=0}^n i^m + \sum_{i=0}^n q_{m-1}(i).\qquad\qquad(*)$$ Let $$q_{m-1}(x) = a_0 x^{m-1} + a_1 x_{m-2} + \dots + a_{m-1} = \sum_{j=0}^{m-1}a_{m-1-j} x^j;$$ then \begin{align*} \sum_{i=0}^n q_{m-1}(i) &= \sum_{i=0}^n \sum_{j=0}^{m-1} a_{m-1-j} i^j\\ &= \sum_{j=0}^{m-1}\sum_{i=0}^n a_{m-1-j} i^j\\ &= \sum_{j=0}^{m-1} a_{m-1-j} \sum_{i=0}^n i^j\\ &= \sum_{j=0}^{m-1} a_{m-1-j} \left(\frac{n^{j+1}}{j+1} + p_j(n) \right) \end{align*} is a polynomial in $n$ of degree at most $m$, which I’ll call $r_m(n)$.

Substitute this into $(*)$: $\displaystyle(n+1)^{m+1} = (m+1)\sum_{i=0}^n i^m + r_m(n)$, so \begin{align*} (m+1)\sum_{i=0}^n i^m &= (n+1)^{m+1} - r_m(n)\\ &= n^{m+1} + s_m(n) - r_m(n), \end{align*} where $s_m$ is a polynomial of degree $m$. Here again I’ve used the binomial theorem. Now $s_m(n) - r_m(n)$ is clearly a polynomial in $n$ of degree at most $m$, so if we set $$p_m(n) = \frac{1}{m+1}(s_m(n) - r_m(n),$$ then $p_m$ is a polynomial of degree at most $m$, and $$\sum_{i=0}^n i^m = \frac{n^{m+1}}{m+1} + p_m(n),$$ as desired.

-

Suppose we know that $$\sum_{i=1}^n\;i^k=\frac{n^{k+1}}{k+1}+P_k(n)$$ where $P_k$ is a polynomial of degree $k$. Sum in $n$ to get \begin{align} \sum_{n=1}^m\;\sum_{i=1}^n\;i^k&=\sum_{n=1}^m\left(\frac{n^{k+1}}{k+1}+P_k(n)\right)\\ \sum_{i=1}^m\;\sum_{n=i}^m\;i^k&=\frac{1}{k+1}\sum_{n=1}^m\;n^{k+1}+Q_{k+1}(m)\\ \sum_{i=1}^m\;(m-i+1)i^k&=\frac{1}{k+1}\sum_{n=1}^m\;n^{k+1}+Q_{k+1}(m)\\ (m+1)\left(\frac{m^{k+1}}{k+1}+P_k(m)\right)-\sum_{i=1}^m\;i^{k+1}&=\frac{1}{k+1}\sum_{n=1}^m\;n^{k+1}+Q_{k+1}(m)\\ (m+1)\left(\frac{m^{k+1}}{k+1}+P_k(m)\right)-Q_{k+1}(m)&=\frac{k+2}{k+1}\sum_{n=1}^m\;n^{k+1}\\ \frac{m^{k+2}}{k+2}+P_{k+1}(m)&=\sum_{n=1}^m\;n^{k+1} \end{align}

-

One approach would be to say "We assume that $\sum_{i=1}^n i^k = \frac{n^{k+1}}{k+1} +$ some terms which are $O(n^k)$ or smaller. Now we try to add $(n+1)^k$. You then use the binomial expansion to show that $\frac{(n+1)^{k+1}}{k+1} = \frac{n^{k+1}}{k+1} + (n+1)^k$ + terms which are $O(n^{k-1})$ or smaller." The problem with this approach as stated is that we place fast and loose with the terms of degree $k$. You can fix that without too much difficulty, but I'll leave that to you.

-

Consider falling factorial polynomial $x^{(k)} = x(x-1)\cdots (x-k+1) = \prod_{i=0}^{k-1} (x+i)$ for $k \in \mathbb{N}$. Then observe that

$$(x+1)^{(k)} - x^{(k)} = (x+1) \cdot x^{(k-1)} - x^{(k-1)} \cdot (x-k+1) = k \cdot x^{(k-1)}$$ That is $x^{(k)} = \frac{1}{k+1} \left( (x+1)^{(k+1)} - x^{(k+1)} \right)$. Thus, the sum in question is really telescoping sum: $$\begin{eqnarray} \sum_{x=0}^n x^{(k)} &=& \frac{1}{k+1} \sum_{x=0}^n \left( (x+1)^{(k+1)} - x^{(k+1)} \right) \\ &=& \frac{1}{k+1} \left( (n+1)^{(k+1)} - 0^{(k+1)} \right) \\ &=& \frac{1}{k+1} (n+1)^{(k+1)} \end{eqnarray}$$ The remaining piece is that $x^m = \sum_{k=1}^m {S}^{(2)}_{n,k} x^{(k)}$, where ${S}^{(2)}_{n,k}$ are Stirling numbers of the second kind. Therefore

$$\sum_{x=0}^n x^k = \sum_{i=1}^k {S}^{(2)}_{k,i} \sum_{x=0}^n x^{(i)} = \sum_{i=1}^k {S}^{(2)}_{k,i} \frac{1}{i+1} (n+1)^{(i+1)}$$ that is the sum is polynomial in $n$ of degree $k+1$, and therefore the leading coefficient is $\frac{1}{k+1}n^{k+1}$.

-