Discrete Mathematics

Summations

Summation is the operation of adding a sequence of numbers; the result is their sum or total.

Overview:

Often mathematical formulae require the addition of many variables. Summation or sigma notation is a convenient and simple form of shorthand used to give a concise expression for a sum of the values of a variable. A summation is simply the act or process of adding.

Examples of summations:

  1. 1 + 2 + 3 + 4 + 5 = 15
  2. 2 + 2 + 2 + 2 = 8
  3. 3 + 6 + 9 = 3( 1 + 2 + 3) = 3(6) = 18
  4. 1+10 + 100 + 1000 = 100 + 101 + 102 + 103 = 1,111

Summation Notation Involves:

  1. The summation sign, S, instructs us to sum the elements of a sequence.
  2. A typical element of the sequence which is being summed appears to the right of the summation sign.
  3. The variable of summation, i.e. the variable which is being summed
  4. The variable of summation is represented by an index which is placed beneath the summation sign.
  5. The index is often represented by i. (Other common possibilities for representation of the index are j and t.) The index appears as the expression i = 1.
  6. The index assumes values starting with the value on the right hand side of the equation and ending with the value above the summation sign.
  7. The starting point for the summation or the lower limit of the summation
  8. The stopping point for the summation or the upper limit of summation

Summations and Algorithm Analysis

randerson112358

Write a summation that represents the value of a variable.

Download PDF

Growth rates

Summations and algorithm analysis of programs with loops goes hand in hand. You can use summations to figure out your program or functions runtime. There are some particularly important summations, which you should probably commit to memory (or at least remember their asymptotic growth rates). For example:The summation from i=1 to n of i = n(n+1) / 2 ==> Θ(n2)

Download PDF

Summations Formulas Description

Here are some of the most commonly used formulas for summations used in computer science.

Summation manipulation properties:

Summation

randerson112358

Learn what sum notation is and solve

Download PDF Download PDF

Code:

/* C Program for a simple summation */


   # include <stdio.h>
   
    int main(void)
    {
       int n = 5, sum = 0, sum2;
       int i;
       
       // A summation can be written as a for loop. Here the loop represents a summation from i=1 to n.
       for( i=1; i<=n; i++)
           sum += i;

      // You can also use the formula to give an answer for sum.
     sum2 = n * (n + 1) / 2;

     printf("sum = %d, and sum2 = %d, they are the same number\n", sum, sum2);
    
     //Comment out the system("pause") if you are not using Windows
     system("pause");
    
    }

Copyright © 2013, Everything Computer Science.