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)=?$$

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

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!

  • $\begingroup$ Thank you for your answer. You really made this clear to me :). $\endgroup$ – Vizualni Mar 1 '12 at 13:40

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.

  • $\begingroup$ Thanks for this refreshingly new perspective. $\endgroup$ – The Chaz 2.0 Mar 1 '12 at 13:59

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



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.

  • $\begingroup$ 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 $\endgroup$ – NoChance Mar 1 '12 at 13:16
  • 1
    $\begingroup$ 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. $\endgroup$ – NoChance Mar 1 '12 at 13:18
  • $\begingroup$ Oh, thanks for pointing that out! $\endgroup$ – user21436 Mar 1 '12 at 13:19
  • $\begingroup$ I was the one who downvoted because it didn't answer the question. You edited it twice by now which makes it better. $\endgroup$ – Gigili Mar 1 '12 at 13:56

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

  • $\begingroup$ Wonderful answer; well researched and well presented. $\endgroup$ – user22805 Mar 20 '12 at 7:16

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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