Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
But $n$ is a variable. –  André Nicolas Sep 8 '11 at 19:01
1  
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. Sep 8 '11 at 19:04
4  
@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
add comment

4 Answers 4

up vote 0 down vote accepted

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.

share|improve this answer
add comment

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} $$

share|improve this answer
add comment

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.

share|improve this answer
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.