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 was wondering if there is any method of turning this (e.g):

$$\sum\limits_{i=1}^k i$$

into this:

$$1 + 2+ 3 +4+\cdots+k=\frac{k(k+1)}{2}\ ?$$

This is know well known formula.

But what if we have something more complex, like this:

$$\sum\limits_{i=1}^k i^2 + 3i$$

$$(1^2+3) + (2^2 + 3\cdot2) + (3^2 + 3\cdot3)+\cdots+(k^2 + 3k)=?$$

share|improve this question
    
The closed formula for the sum $\sum\limits_{i=1}^k i^2$ is proved in this question. –  Américo Tavares Mar 1 '12 at 13:21
    
Thank you all for your answers :). –  Vizualni Mar 1 '12 at 13:40
add comment

6 Answers

up vote 8 down vote accepted

There are properties of series that can be used. Specifically, series are linear, which means $$ \sum_{i=1}^k (ca_i + b_i) = c\sum_{i=1}^k a_i + \sum_{i=1}^k b_i, $$ for constants $c$. Thus, $$ \sum_{i=1}^k (i^2 + 3i) = \sum_{i=1}^k i^2 + 3\sum_{i=1}^k i.$$ At that point, you need the formulas, $$ \sum_{i=1}^k i^2 = \frac{k(k+1)(2k+1)}{6}, \qquad \sum_{i=1}^k i = \frac{k(k+1)}{2}.$$ So we obtain: $$ \sum_{i=1}^k (i^2 + 3i) = \ldots = \frac{k(k+1)(2k+1)}{6} + \frac{3k(k+1)}{2}.$$ Now what if we didn't have those two formulas? Well the sum of consecutive integers can be thought of as a "averaging" formula. Since $1, 2, 3, \ldots, k$ is an arithmetic sequence, $$1+2+3+ \cdots + k = (\textrm{average of}\; 1, 2, 3, \ldots, k) \cdot k.$$ (convince yourself this is true by looking at small $k$ values.) Furthermore, the average is the "middle" number of the arithmetic sequence, if $k$ is odd, or the average of the two middles if $k$ is even. Either way, the value $\frac{k+1}{2}$ is the average (it balances out the values on the left and right of it). So that $$1+2+3+ \cdots + k = \frac{k+1}{2} \cdot k = \frac{k(k+1)}{2}.$$ Now the sum of consecutive squares can't be handled quite the same way. However, you can prove inductively that $$ \sum_{i=1}^k i^p = (\textrm{polynomial in $k$, of degree $p+1$}). $$ So $\sum_{i=1}^k ak^3 + bk^2 + ck + d$. Then use the first four values, $\sum_{i=1}^1 i^2 = 1$, $\sum_{i=1}^2 i^2 = 5$, etc. to determine $a, b, c, d.$ Anyway, that is how one can find the formula $\sum_{i=1}^k i^2= \frac{k(k+1)(2k+1)}{6}$, after which we simply memorize to use it in the future.

Hope this helps!

share|improve this answer
    
Thank you for your answer. You really made this clear to me :). –  Vizualni Mar 1 '12 at 13:40
add comment

There are indeed methods of dealing with many more complicated summations; the excellent book Concrete Mathematics, by Graham, Knuth, & Patashnik, is full of such techniques. One of them is finite calculus; this PDF contains a decent brief introduction using the notation of Concrete Mathematics.

One of the basic results of finite calculus is that $$\sum_{k=a}^bk^{\underline{m}}=\left[\frac{k^{\underline{m+1}}}{m+1}\right]_a^{b+1}\;,$$ where $x^{\underline{m}}=x(x-1)(x-2)\cdots(x-m+1)$ is called a falling power of $x$.

Note the similarity with $$\int_a^bx^m dx=\left[\frac{x^{m+1}}{m+1}\right]_a^b\;,$$ though there is a difference in the upper limit of evaluation.

In this case we write $k^2=k(k-1)+k=k^{\underline{2}}+k^{\underline{1}}$, so that $$\sum_{k=1}^nk^2=\sum_{k=1}^n(k^{\underline{2}}+x^{\underline{1}})\;,$$ and

$$\begin{align*}\sum_{k=1}^n(k^2+3k)&=\sum_{k=1}^n(k^{\underline{2}}+4x^{\underline{1}})\\ &=\sum_{k=1}^nk^{\underline{2}}+4\sum_{k=1}^nx^{\underline{1}}\\ &=\left[\frac{k^{\underline{3}}}3\right]_1^{n+1}+4\left[\frac{k^{\underline{2}}}2\right]_1^{n+1}\\ &=\frac13\left((n+1)^{\underline{3}}-1^{\underline{3}}\right)+2\left((n+1)^{\underline{2}}-1^{\underline{2}}\right)\\ &=\frac13(n+1)^{\underline{3}}+2(n+1)^{\underline{2}}\\ &=\frac13(n+1)n(n-1)+2(n+1)n\\ &=n(n+1)\left(\frac{n-1}3+2\right)\\ &=\frac{n(n+1)(n+5)}3\;. \end{align*}$$

This may look a little complicated, but once you have the basic tools of finite calculus, which aren’t actually very hard, you can generalize this to all sorts of polynomial sums and even beyond that.

share|improve this answer
    
Thanks for this refreshingly new perspective. –  The Chaz 2.0 Mar 1 '12 at 13:59
    
+1, Very informative, thanks. –  Emmad Kareem Mar 1 '12 at 14:11
add comment

Prove by induction that:

$$\sum\limits_{i=1}^k i= 1 + 2+ 3 +4+...+k=\frac{k(k+1)}{2}$$

If it holds for $k$, it should be true for $k+1$:

$$\sum\limits_{i=1}^{k+1} i= \color{red}{1 + 2+ 3 +4+...+k}+(k+1)=\frac{k(k+1)}{2}+k+1=\frac{(k+1)(k+2)}{2}$$

The same applies for your second question: $$\sum\limits_{i=1}^k i^2 + 3i$$

$$=\sum\limits_{i=1}^k i^2+ 3\sum\limits_{i=1}^k i$$

$$=\frac{k(k+1)(k+2)}{6}+3(\frac{k(k+1)}{2})$$

share|improve this answer
add comment

Verify the following equation. And, note that index runs over only upto a finite stage. Because, this is false for many infinite cases (as I indicate at the end!)

$$\sum_{i=1}^n (a_i+b_i)=\sum_{i=1}^n a_i+\sum_{i=1}^n b_i\\\ \sum_{i=1}^nc\cdot a_i=c\cdot\left(\sum_{i=1}^na_i\right)$$

where $c$ is a constant independent of the running index.

So, the desired sum becomes, $$\sum_{i=1}^k (i^2+3i)=\sum_{i=1}^ki^2+3\sum_{i=1}^k i$$

As you have noted, you can now use, $\displaystyle\sum_{i=1}^ki=\dfrac{k(k+1)}{2}$ and $\displaystyle\sum_{i=1}^ki^2=\dfrac{k(k+1)(2k+1)}{6}$ to get the sum.


Here is what I mean when I talk about the infinite series:

$$\sum_{i=1}^\infty (i-i)=\sum_{i=1}^\infty 0=0$$ but when you expand the sum as I wrote down above, you'll get $\infty-\infty$ which clearly refuses to make sense!


That you call this complicated, I am inclined to give you some references, which if you're Mathematically inclined, you'll love.

Suggested Reading:

  • Terry Tao -- Analysis, Volume I, TRIM series, Hindustan Book Agency.(here) for errata and some links

  • Knopp -- Infinite sequence and Series, Dover Books on Mathematics (here)

  • Thomas Bromwich -- An Introduction to the theory of Infinite Series (archive.com link)

You may like this answer of mine in connection with the last reference.

share|improve this answer
    
if the OP wants to see how the sum for $i^2$ is evaluated as it is see for example: jimloy.com/algebra/gseries.htm –  Emmad Kareem Mar 1 '12 at 13:16
1  
the general problem asks for $\sum_{i=1}^k (i^2+3i)$ not $\sum_{i=1}^k (i^2+i)$ please adjust the solution accordingly. –  Emmad Kareem Mar 1 '12 at 13:18
    
Oh, thanks for pointing that out! –  user21436 Mar 1 '12 at 13:19
    
I was the one who downvoted because it didn't answer the question. You edited it twice by now which makes it better. –  Gigili Mar 1 '12 at 13:56
    
+1 for the added references. –  Emmad Kareem Mar 1 '12 at 14:06
show 1 more comment

My approach will look like overkill for your particular problem, but you asked for the general method of summation such series.

If you can find explicit formula for series of the form $S_r(k)=\sum\limits_{i=0}^k i^r$, $r\in\mathbb{Z}_+$ then you can find formula for the series of the form $\sum\limits_{i=1}^k P_n(i)$, where $P_n(x)$ is the polynomial of degree $n$. Indeed, if $P_n(x)=\sum\limits_{r=1}^n a_r x^r$, then $$ \sum\limits_{i=1}^k P_n(i)= \sum\limits_{i=1}^k \sum\limits_{r=1}^n a_r i^r= \sum\limits_{r=1}^n a_r \sum\limits_{i=1}^k i^r= \sum\limits_{r=1}^n a_r S_r(k) $$ So the question is how to compute $S_r(k)$. This can be made by recurrence formula. For the begining $$ S_0(k)=\sum\limits_{i=0}^k i^0=k+1 $$ Now to derive recurrence formula note that $$ (i+1)^{r+1}-i^{r+1}= \left(\sum\limits_{p=0}^{r+1} {r+1 \choose p} 1^{r+1-p} i^p\right) -i^{r+1}= $$

$$ \left(\sum\limits_{p=0}^{r+1} {r+1 \choose p} i^p\right) -i^{r+1}= \sum\limits_{p=0}^{r} {r+1 \choose p} i^p $$ Now lets sum this equalities by $i$ from $0$ to $k$. Then we get $$ \sum\limits_{i=0}^{k} \left((i+1)^{r+1}-i^{r+1}\right)= \sum\limits_{i=0}^{k} \sum\limits_{p=0}^{r} {r+1 \choose p} i^p= \sum\limits_{p=0}^{r} {r+1 \choose p}\sum\limits_{i=0}^{k} i^p= \sum\limits_{p=0}^{r} {r+1 \choose p}S_p(k)= $$ $$ {r+1 \choose r}S_{r}(k)+\sum\limits_{p=0}^{r-1} {r+1 \choose p}S_p(k)= (r+1)S_{r}(k)+\sum\limits_{p=0}^{r-1} {r+1 \choose p}S_p(k) $$ Note that $\sum\limits_{i=0}^{k} \left((i+1)^{r+1}-i^{r+1}\right)$ is a telescopic sum and it is equals to $(k+1)^{r+1}$. So we get the following equality $$ (k+1)^{r+1}=(r+1)S_{r}(k)+\sum\limits_{p=0}^{r-1} {r+1 \choose p}S_p(k) $$ This gives us $$ S_r(k)=\frac{1}{r+1}\left((k+1)^{r+1}-\sum\limits_{p=0}^{r-1} {r+1 \choose p}S_p(k)\right) $$ From this formula one can show by induction that $S_r(k)$ is a polynomial of variable $k$ of degree $r+1$. Coefficients of this polynomial is strongly related to so called Bernoulli numbers, denoted by $B_n$. In fact, $$ S_r(k)=\frac{1}{r+1}\sum\limits_{i=0}^{r}{r+1\choose i}B_i k^{r+1-i} $$ The first Bernoulli numbers are: $B_0=1$, $B_1=-1/2$, $B_2=1/6$, $B_3=-1/30$ et cetera.

Now we return to the original problem $$ S_1(k)= \frac{1}{2}\left((k+1)^2-\sum\limits_{p=0}^{0} {2 \choose p}S_p(k)\right)= \frac{1}{2}\left((k+1)^2-{2 \choose 0}S_0(k)\right)= \frac{1}{2}\left(k^2+2k+1-(k+1)\right)=\frac{k^2+k}{2}=\frac{k(k+1)}{2} $$ and $$ S_2(k)= \frac{1}{3}\left((k+1)^{3}-\sum\limits_{p=0}^{1} {3 \choose p}S_p(k)\right)= \frac{1}{3}\left((k+1)^{3}-{3 \choose 0}S_0(k)-{3 \choose 1}S_1(k)\right)= \frac{1}{3}\left((k+1)^{3}-(k+1)-3\frac{k^2+k}{2}\right)= \frac{2k^3+3k^2+k}{6}=\frac{k(2k+1)(k+1)}{6} $$ Finally $$ \sum\limits_{i=1}^k(i^2+3i)= \sum\limits_{i=1}^k i^2+3\sum\limits_{i=1}^k i= $$ $$ S_2(k)+3S_1(k)= \frac{2k^3+3k^2+k}{3}+\frac{k^2+k}{2}= \frac{k^3+6 k^2+5 k}{3}= \frac{k (k+1) (k+5)}{3} $$

share|improve this answer
    
Wonderful answer; well researched and well presented. –  user22805 Mar 20 '12 at 7:16
add comment

More generally, you can set $f(k) = \sum_{i=1}^k a_i$, and then you get the recurrence equation $f(k) = f(k-1) + a_k$, with $f(1)$ known. Now solve the recurrence equation, and you have the formula you're looking for.

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.