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?
Thank you in advance for your help.
 A: 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}
$$
A: 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.
A: 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.
A: 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}$.
