What is summation?

In mathematics, the summation is the process of adding a sequence of numeric values, known as addends and their result is called sum or total. The term summation refers to the addition or sum of two or more numbers or units. For example-

Sum = 1+2+3+4+5

This is the sum of digits from 1 to 5 in a sequence. The total of these numbers is 15. This is a straightforward computation. In the above calculation, the numbers or sequences can be written one after the other using the plus (+) symbol (addition symbol), such as 1+2+3+4+5. However, it is difficult to write all the elements when the sequence of numbers is quite long and the summation has numerous terms.

To avoid this, a summation symbol was devised in mathematics. This summation symbol is a large, uppercase, Greek letter sigma ∑ . The notation is described in the figure below.

An example of summation notation is -

$\sum _{n=1}^{100}n$

Here, $n=1$ is the lower bound of the summation. It is the initial or starting number or first term of the sequence. $n=100$ is the upper bound of summation which is the end limit of summation and $n$ (argument) indicates the sequence of numbers like 1,2,3,4----100.  The value of $n$ is always an integer number and it increases by 1 for each succeeding term.

Suppose that if the summation has no limit which means the summation has no upper bound. Then the summation goes to the infinite limit such that the summation starts from  $n=1$ to unlimited value of  $n$, that is 1+2+3+4+5+----------------, which is denoted as follows:

$\sum _{n=1}^{\infty } n$

In this notation, the infinity symbol is used. The $\infty$ symbol is known as infinite. The upper bound $n = \infty$ shows that $n$ continue to increase without limit. So, it is the summation of $1$ to infinity. 

Summation function

The summation is used to examine the continuity of addition. Suppose $f\left(x\right)$ is a function. The summation of a function $f\left(x\right)$ from $x = a$ to $x = b$ where $a, b$ is the lower bound and upper bound of summation respectively. An example of a summation function is:

$\begin{array}{rcl}f\left(x\right) & =& \sum _{n=1}^3 (n+1)\\ y & =& f\left(x\right)\\ y & =& \sum _{n=1}^3 (n+1)\\ y & =& (1+1)+(2+1)+(3+1)\\ y & =& 2+3+4\\ y & =& 9\end{array}$

Here $\sum _{n=1}^3 (n+1)$ is the summation function. The result of this function 9. This function is bounded from 1 to 3.

If summation has an infinite sequence, then it is called a series. The summation is of two types- divergent summation and convergent summation. If the summation is not bounded by any digit or a fixed number then it is called divergent summation because the sum expands without the limit. If summation is bounded with limits or numbers then it is called convergent summation.

Bounded summation

There are a variety of ways for bounding the summations that define algorithm execution times. Here are a few of the most popular approaches. The bounded summation satisfies many theorems.

Mathematical induction of bounded summation

Mathematical induction is the most basic method for evaluating a series For example- The arithmetic series $\sum _{i=1}^n i^2$ evaluates to $1/6 n(n+1)(2n+1)$.  If we put $n=1$, we can easily verify this series. As a result, we make the inductive assumption that it holds for n and prove it for $n+1$. We have got:

$\begin{array}{rcl}\sum _{i=1}^{n+1} i^2 & =& \sum _{i=1}^n i^2 + {(n+1)}^2\\ & =& \frac{1}{6}n(n+1)(2n+1) + (n^2+2n+1)\\ & =& \frac{n(n+1)(2n+1)+6(n^2+2n+1)}{6}\\ & =& \frac{2n^3+9n^2+13n+6}{6}\\ & =& \frac{(n+1)(n+2)(2n+3)}{6}\end{array}$

So, it is true for $n+1$. To apply mathematical induction, one does not need to guess the exact value of a summation. Induction can also be used to demonstrate a bound. For another example the let us prove that geometric series $\sum _{i=0}^n 2^i$ is $O\left(2^n\right)$. Prove $\sum _{i=0}^n{2}^i \le c{2}^n$ for some constant c. if we put $n=0$, then $\sum _{i=0}^0{2}^i = 1 \le c·1$ as long as $c \ge 1$. Let us assume that the bound holds for $n$ and then show that it also holds for $n+1$. We have got:

$\begin{array}{rcl}\sum _{i=0}^{n+1} 2^i & =& \sum _{i=0}^n 2^i + 2^{n+1}\\ & =& c 2^n + 2^{n+1}\\ & =& (\frac{1}{2}+\frac{1}{c}) c 2^{n+1}\\ & \le & c 2^{n+1}\end{array}$

The value of $(1/2 + 1/c) \le 1$ or $c \ge 2$ so $\sum _{i=0}^n 2^i = O\left(2^n\right)$, as we wanted to prove. This is the concept of bounded summation.

When using asymptotic notation to prove boundaries via induction, we must be cautious. Take a look at the following fallacious proof, that $\sum _{i=1}^n i = O\left(n\right)$. Certainly, $\sum _{i=1}^1 i = O\left(1\right)$. Assuming the bound for $n$, we now prove it for $n+1$:

$\begin{array}{rcl}\sum _{i=1}^{n+1} i & =& \sum _{i=1}^n i + (n+1)\\ & =& O\left(n\right) + O(n+1)\\ & =& O(n+1)\end{array}$    <= wrong!!!

The error in the argument is that the "constant" concealed by the "big-oh" expands with n and is hence not constant. We have not demonstrated that the same constant applies to all n.

Use of integration for the Summation

The integration is defined as the summation of values. A definite integral has a limit whereas the indefinite integral works similar to unbounded summation. See the figure below. The area is bounded by the x-axis and a and b are the limits of the area. The curve function is $y = f\left(x\right)$.

There are numerous methods for estimating this area. Assume we divide the area into thin vertical stripes, similar to the one illustrated, and each strip is roughly rectangular. The area under the curve is then approximated by adding the areas of the rectangular strips. 

From the point P, a standard strip is drawn $p\left(x,y\right)$. The width of the strip is indicated by the letter $∆x$. The sign $∆$ is used to represent a modest rise in the variable being analyzed, in this case, x. The strip's height is equal to the curve's $y$ value at point P, which is$f\left(x\right)$. As a result, the area of the strip illustrated is roughly $f\left(x\right)·∆x$. Assume that the area of this little strip is equal $∆A$. Because this strip contributes a minor amount $A$, to the total area $∆A$, under the curve, we employ the delta notation once more. Then

$∆x \approx f\left(x\right)∆x$

We may calculate the entire area under the curve by adding the areas of all such thin strips from $a$ to $b$, which we represent by $\sum _{x=a}^b∆x$.

$Total Area =\sum _{x=a}^b ∆x\approx \sum _{x=a}^{b}f\left(x\right)∆x$

To improve the accuracy of this approximation, we must reduce the thickness of each strip to a very small value, i.e. we let $∆x\to 0$, giving

$Total area =\underset{∆x\to 0}{\lim } \sum _{x=a}^{b}f\left(x\right)∆x$

This is referred to as a sum's limit. If there is a limit, we will write it as${\int }_a^{b}f\left(x\right)∆x$. As a result, a definite integral is defined as the limit of a sum. As a result, we get the significant result that

${\int }_a^{b}f\left(x\right)∆x =\underset{∆x\to 0}{\lim } \sum _{x=a}^{b}f\left(x\right)∆x$

Therefore, integration might be thought of as a process of adding up or summarizing.

Concepts and Applications

This topic is significant in the professional exams for both graduate and postgraduate courses, especially for:

• Bachelor of Technology in Computer Science
• Master of Technology in Computer Science

Related Concepts

• Summation notation
• Summation algorithm
• Convergence summation
• Divergence summation

Practice Problems

Q1. What is the symbol of summation-

1. 1. $\cap$
   2. $\sum _{}^{}$
   3. $\prod _{}^{}$
   4. $\cup$

Correct answer- 2. $\sum _{}^{}$

Explanation-  $\sum _{}^{}$ is the symbol of addition used to add a large sequence.

Q2. What is the value of $\sum _{i=0}^n (10 + i)$ if i = 0.

1. 1. 10
   2. 10+n
   3. n+10
   4. 0

Correct answer- 1. 10

Explanation- If i = 0,

$\begin{array}{rcl}& & \sum _{i=0}^n (10 + i)\\ & =& \sum _{i=0}^n (10 + 0)\\ & =& \sum _{i=0}^n 10 (10 is a cons\tan t)\\ & =& 10\end{array}$

Q3. If the summation is not bound by any limit then this is known as:

1. 1. Convergent
   2. Divergent
   3. None
   4. Infinite

Correct answer- 2. Divergent

Explanation- A divergent series is an infinite series that is not convergent, which means that the infinite sequence of partial sums of the series has no finite limit in mathematics. 

Q4. The value of finite series is always:

1. 1. non-defined
   2. well-defined
   3. none
   4. integral

Correct answer- 2. well-defined

Explanation- "Well-defined" means that the total exists and equals the same real number regardless of the sequence in which the terms are added.

Q5. Which statement is false:

1. A Cauchy sequence of real numbers need not be bounded.
2. A sequence of real numbers need not be bounded.
3. A sequence of real numbers is convergent if and only if it is a Cauchy sequence.
4. The series $\sum _{n=1}^{\infty }\frac{1}{n^2}$ is convergent.

Correct answer- 1. A Cauchy sequence of real numbers need not be bounded.

Explanation- Every Cauchy sequence of real numbers has a convergent subsequence, and so is itself convergent, according to Bolzano–Weierstrass. The least upper bound axiom is implicitly used in this demonstration of the completeness of the real numbers.