SUMMATION

Lecture # 14
 INTRODUCTION
 SERIES:
The sum of the terms of a sequence forms a series. If
a1, a2, a3, …

represent a sequence of numbers, then the corresponding

series is:
a1 + a2 + a3 + …


= a
k 1
k
 SUMMATION NOTATION
 The capital Greek letter sigma  is used to write a sum
in a short hand notation.


 Hence  ak represents the sum given in expanded

k 1
form by


a
k 1
k = a1 + a2 + a3 + … + a n

Here k is called the index of the summation;

Lower limit of the summation is 1.
Upper limit of the summation is .
 More generally if m and n are integers and m  n, then
the summation from k equal m to n of ak is
n

a
k m
k  am  am 1  am  2   an

 where k varies from 1 to n represents the sum given in

expanded form by
 COMPUTING SUMMATIONS
 Let a0 = 2, a1 = 3, a2 = -2, a3 = 1 and a4 = 0.
Compute each of the summations:

4 2 1
1. a
i 0
i 2. a
j 0
2j 3. a
k 1
k
SOLUTION
Let a0 = 2, a1 = 3, a2 = -2, a3 = 1 and a4 = 0
We will take i = 0, 1, 2, 3, 4
4

1. a
i 0
i = a 0 + a1 + a2 + a3 + a4

4 = 2 + 3 + (-2) + 1 + 0
 ai = 4
i 0
SOLUTION
Let a0 = 2, a1 = 3, a2 = -2, a3 = 1 and a4 = 0
We will take j = 0, 1, 2
2

2. a
j 0
2j = a 0 + a2 + a4

2 = 2 + (-2) + 0
 a2 j = 0
j 0
SOLUTION
Let a0 = 2, a1 = 3, a2 = -2, a3 = 1 and a4 = 0
We will take k = 1
1

3. a
k 1
k = a1

1 =3
 ak = 3
k 1
 EXERCISE
 Compute the summations.
3
1.  (2i  1)
i 1
 [2(1)  1]  [2(2)  1]  [2(3)  1]

 1  3 5
 9
1
2.  (k
k 1
3
 2)  [( 1)3  2]  [(0)3  2]  [(1)3  2]

 [1  2]  [0  2]  [1  2]
 1 2 3
 6
 NOTE
 Note that in both the examples we have constants.

 In First example we have constant ‘-1’ that constant

appear in all three terms.

 Similarly ‘+2’ in the second example.

 The constant term in series keep on adding.

 SUMMATION NOTATION TO
EXPANDED FORM
 Write the summation 
n
( 1) i
to expanded form:
i 0 i  1
 SOLUTION:

Lower Limit = 0, Upper Limit = n

Total number of terms will be n + 1.
n
(1)i (1)0 (1)1 (1) 2 (1)3 ( 1) n

i 0 i  1
   
0 1 11 2 1 3 1
 
n 1
1 (1) 1 (1) (1) n
     
1 2 3 4 n 1
1 1 1 (1) n
 1    
2 3 4 n 1
 EXPANDED FORM TO SUMMATION
NOTATION
 Write the following using summation notation:
1 2 3 n 1
1.    
n n 1 n  2 2n
 SOLUTION
Terms Numerators
For first term 1
For second term 2
For third term 3
…… …...
…… …...
For last term n+1
 Terms Denominator
For first term n
For second term n+1
For third term n+2
…… …...
…… …...
For last term 2n
 1, 2, 3,…, n+1 are Numerators
 The numerators forms an arithmetic sequence
a = first term = 1
& d = common difference = 1

n, n+1, n+2, …, 2n are Denomenators.

 Similarly, denominators forms an arithmetic sequence
a = first term = n
d = common difference = 1
 For Numerator the kth term will be:
ak = a + (k - 1)d
= 1 + (k - 1) (1)
=1+k-1
ak = k

For Denominator the kth term will be:

ak = a + (k - 1)d
= n + (k - 1) (1)
ak = k + n – 1
 Hence the kth term of the series is
k
(n  1)  k
 And the expression for the series is given by
1 2 3 n  1 n 1 k
     
n n 1 n  2 2n k 1 ( n  1)  k
n
k 1

k 0 n  k
 REMARK
3
Consider    
2 2 2 2
k 1 2 3
k 1
3

And  i
i 1
2
 12
 2 2
 32

3 3
Hence  
k 2

k 1
 i 2

i 1

The index of a summation can be replaced by any other

symbol. The index of a summation is therefore called a
dummy variable.
 EXERCISE
 Simplify the variables in summation as simplified as
possible. n 1
k
 Consider  k 1 ( n  1)  k

If we put k = j + 1 then the denominator simplifies.

Substituting k = j + 1 so that j = k – 1

When k = 1, j = k - 1 = 1 - 1 = 0
When k = n + 1, j = k - 1 = (n + 1) - 1 = n
When k varies from 1 to n + 1 then j varies from 0 to n.
 We put j instead of k and summation becomes:
n 1
k n
j 1

k 1 (n  1)  k
 
j 0 (n  1)  ( j  1)

n
j 1 n k 1
  (changing variable)
j 0 n  j k 0 n  k
 EXERCISE
 Transform by making the change of variable j = i - 1, in the
summation:
n 1
i

i 1 ( n  i )
2
SOLUTION

Set j  i  1 so that i  j  1
when i  1
j  i 1  11  0
when i  n  1
j  i  1  ( n  1)  1  n  2
n 1
i n2
j 1
  
i 1 ( n  i ) j  0 ( n  ( j  1))
2 2

n2
j 1

j  0 ( n  j  1)
2
 PROPERTIES OF SUMMATIONS
n n n
1.  (a
k m
k  bk )   ak   bk ;
k m k m
ak , bk  R
n n
2.  ca
k m
k  c  ak
k m
c R

b i b
3.  (k  i )   k
k  a i k a
iN
b i b
4.  (k  i )   k
k  a i k a
iN

n
5. c 
k 1
cc  c  nc
 EXERCISE
 Express the following summation more simply:
n n
3 (2k  3)   (4  5k )
k 1 k 1

 SOLUTION:
n n
3 (2k  3)   (4  5k )
k 1 k 1
 n n
 3 (2k  3)   (4  5k )
k 1 k 1
n n
 3 (2k  3)   (4  5k )
k 1 k 1
n
  [3(2k  3)  (4  5k )]
k 1
n
  ( k  5)
k 1
n n
  k  5
k 1 k 1
n
  k  5n
k 1
 ARITHMETIC SERIES
 The sum of the terms of an arithmetic sequence forms an
arithmetic series (A.S).
 For example:

Arithmetic sequence is 1 , 3 , 5 , 7 , …
Then
1+3+5+7+…

is an arithmetic series of positive odd integers.

 In general, if a is the first term and d the common
difference of an arithmetic series, then the series is given
as:

a + (a+d) + (a+2d) +…
SUM OF n TERMS OF AN ARITHMETIC
SERIES
 Let a be the first term and d be the common difference of
an arithmetic series. Then its nth term is:
an = a + (n - 1)d; n1

If Sn denotes the sum of first n terms of the A.S, then

Sn = a + (a + d) + (a + 2d) + … + [a + (n-1) d]
= a + (a+d) + (a + 2d) + … + an
Where an = a + (n - 1)d
= a + (a+d) + (a + 2d) + … + (an - d) + an …(1)
 Rewriting the terms in the series in reverse order.
Sn = an + (an - d) + (an - 2d) + … + (a + d) + a ……….(2)
Adding (1) and (2) term by term, gives
2Sn = (a + an) + (a + an) + (a + an) + … + (a + an)
(n terms)
2Sn = n(a + an)
Sn = n(a + an)/2
If we write an = a + (n - 1)d
Sn = n(a + l)/2…………………..(3)
Therefore
Sn= n/2 [a + a + (n - 1) d]
Sn = n/2 [2 a + (n - 1) d]……….(4)
 We have two formulas for finding a sum.

Sn = n(a + I)/2 …………..(1)

We use it when we are given first term a and the last

term l.

Sn = n/2 [2a + (n - 1) d] ...................(2)

We will use it when first term and common difference is

given.
 EXERCISE
 Find the sum of first n natural numbers.
 SOLUTION

Let Sn = 1 + 2 + 3 + … + n

Clearly the right hand side forms an arithmetic series

with

a = 1, d = 2 - 1 = 1 and n = n
 n
 Sn   2a  (n  1)d 
2
n
  2(1)  (n  1)(1)
2
n
  2  n  1
2
n(n  1)

2
 EXERCISE
 Find the sum of all two digit positive integers which are
neither divisible by 5 nor by 2.
 SOLUTION
The series to be summed is:
11 + 13 + 17 + 19 + 21 + 23 + 27 + 29 + … + 91 + 93 +
97 + 99
which is not an arithmetic series.
11 + 21 + 31 + ……… + 91 is an arithmetic series.
with a = 11, d = 10
13 + 23 + 33 + ……… + 93 is an arithmetic series.
with a = 13, d = 10
17 + 27 + 37 + ……… + 97 is an arithmetic series.
with a = 17, d = 10
19 + 29 + 39 + ……… + 99 is an arithmetic series.
with a = 19, d = 10

If we make group of four terms we get

(11 + 13 + 17 + 19) + (21 + 23 + 27 + 29) + (31 + 33 +
37 + 39) + … + (91 + 93 + 97 + 99)
= 60 + 100 + 140 + … + 380
which now forms an arithmetic series in which
a = 60; d = 100 - 60 = 40 and l = an = 380
 To find n, we use the formula
an = a + (n - 1) d
 380 = 60 + (n - 1) (40)
 380 - 60 = (n - 1) (40)
 320 = (n - 1) (40)
320
 n 1
40
8=n-1
 n=9
 Now
a = 60 1 = an = 380 n=9
n
Sn  (a  l )
2
9
 S9  (60  380)  1980
2
 GEOMETRIC SERIES
 The sum of the terms of a geometric sequence forms a
geometric series (G.S.).

 For example
Geometric Sequence
1, 2, 4, 8, 16, …
Geometric Series
1 + 2 + 4 + 8 + 16 + …
 In general, if a is the first term and r the common ratio of
a geometric series, then the series is given as:

a + ar + ar2 + ar3 + …
 SUM OF n TERMS OF A GEOMETRIC
SERIES
 Let a be the first term and r be the common ratio of a
geometric series. Then its nth term is:

an = arn-1; n1

If Sn denotes the sum of first n terms of the G.S. then

Sn = a + ar + ar2 + ar3 + … + arn-2 + arn-1….(1)
Multiplying both sides by r we get.
r Sn = ar + ar2 + ar3 + … + arn-1 + arn….(2)
 Subtracting (2) from (1) we get
Sn – rSn = a – arn

 (1 - r) Sn = a (1 - rn)

a(1  r n )
 Sn  (r  1)
1 r
 EXERCISE
 Find the sum of the geometric series
2 2
62    to 10 terms
3 9

 SOLUTION

2 1
a  6, r   and n  10
6 3
 a(1  r n )
 Sn 
1 r
  1 10 
6 1      6 1  1 
  3   10 
    
3
S10
 1  4
1     
 3  3
 1 
9 1  10 
 
3 
2
 RECURRENCE RELATION
 A recurrence relation for a sequence a0, a1, a2, . . . , is a
formula that relates each term ak to certain of its
predecessors ak-1, ak-2, . . . , ak-i , where i is a fixed integer
and k is any integer greater than or equal to i.

 The initial conditions for such a recurrence relation

specify the values of
a0, a1, a2, . . . , ai-1.
 EXAMPLE
 Let {an} be a sequence that satisfies the recurrence
relation an = an-1 +3 for n = 1, 2, 3, …, and suppose that
a0 = 2. What are a1 , a2 , a3 ?

Solution:

an = an-1 +3
a1 = a0 +3
a1 = 2 +3 = 5
a2 = a1 +3
a2 = 5 +3
a2 = 8

a3 = a2 +3
a3 = 8 +3
a3 = 11
 EXAMPLE
 Let {an} be a sequence that satisfies the recurrence
relation an = an-1 - an-2 for n = 2, 3, 4, … and suppose that
a0 = 3 and a1 = 5. What are a2 , a3 ?

Solution:
an = an-1 – an-2
a2 = a1 – a0
a2 = 5 – 3 = 2
a3 = a2 – a1
a3 = 2 – 5 = – 3
 THE FIBONACCI SEQUENCE
 The Fibonacci sequence is defined as follows.
- BASE
F0 = 0, F1 = 1
- Recursion
Fk = Fk-1 + Fk-2 for all integers k  2

F 2 = F 1 + F0 = 1 + 0 = 1
F 3 = F 2 + F1 = 1 + 1 = 2
F4 = F3 + F2 = 2 + 1 = 3
F 5 = F 4 + F3 = 3 + 2 = 5
…
 EXAMPLE
 Determine whether the sequence {an}, where an = 3n for
every nonnegative integer n, is a solution of the
recurrence relation that satisfies the recurrence
relation an = 2an-1 - an-2 for n = 2, 3, 4, … suppose that

Solution:
Suppose that an = 3n for every nonnegative integer n.
an = 2an-1 - an-2
So,
an-1 = 3(n-1)
an-2 = 3(n-2)
 an = 2an-1 – an-2
an = 2(3(n – 1)) – 3(n – 2)
an = 2(3n – 3) – 3n + 6
an = 6n – 6 – 3n + 6
an = 3n

So an = 3n is solution of recurrence relation.

 EXAMPLE
 Determine whether the sequence {an}, where an = 2n for
every nonnegative integer n, is a solution of the
recurrence relation that satisfies the recurrence
relation an = 2an-1 - an-2 for n = 2, 3, 4, … suppose that

Solution:
Suppose that an = 2n for every nonnegative integer n.
an = 2an-1 - an-2
So,
an-1 = 2n-1
an-2 = 2n-2
 an = 2an-1 – an-2
an = 2. 2n-1 –2n-2
an = 2n-1+1 – 2n-2
an = 2n – 2n-2

So an = 2n is not a solution of recurrence relation.

 EXAMPLE
 Determine whether the sequence {an}, where an = 5 for
every nonnegative integer n, is a solution of the
recurrence relation that satisfies the recurrence
relation an = 2an-1 - an-2 for n = 2, 3, 4, … suppose that

Solution:
Suppose that an = 5 for every nonnegative integer n.
an = 2an-1 - an-2
So,
an-1 = 5
an-2 = 5
 an = 2an-1 – an-2
an = 2 . 5 – 5
an = 10 – 5
an = 5

So an = 5 is a solution of recurrence relation.