SUBJECT : DISCRETE MATHEMATICS

BRANCH : COMPUTER SCIENCE AND ENGINEERING

SEMESTER : III
UNIT II : COMBINATORICS
TOPIC : PERMUTATION AND COMBINATION

Presented by
[Link]
Associate Professor
Department of Mathematics
Sri Eshwar College of Engineering

Prepared by [Link] 1
 MODULE II
COMBINATORICS

Permutations and combinations – Inclusion and

exclusion principle - Pigeonhole principle -
Mathematical induction - Recurrence relations -
Solving linear recurrence relations using
generating function.

CO2: Use induction techniques, generating

functions and basics of counting to solve
mathematical statements.
Prepared by [Link] 3
Prepared by [Link] 4
Prepared by [Link] 5
Prepared by [Link] 6
Prepared by [Link] 7
Prepared by [Link] 8
Prepared by [Link] 9
Prepared by [Link] 10
Prepared by [Link] 11
PROBLEMS ON PERMUTATION

Prepared by [Link] 12
Prepared by [Link] 13
Find the number of distinct permutations that can be
formed from all the letters of each word
(i) RADAR (ii) UNUSUAL
Solution:
(i) The word RADAR contains five letters of which two A’s and two R’s
are there.
5!
Therefore the number of possible words = = 30
2! 2!

Number of distinct permutations = 30

(ii) The word UNUSUAL contains 7 letters of which 3 U’s are there.
7!
The number of possible words = = 840.
3!

Number
Number of distinct
of distinct permutations
permutations = 840 = 840

Prepared by [Link] 14
There are 3 red balls , 4 green balls and 5 blue balls in
a bag. They are arrange one by one and arranged in a
row. Assuming that all the 12 balls are drawn,
determine the number of different arrangements.

Solution:

Total number of balls = 3+4+5 = 12

12!
Required number of arrangements =
3! 4! 5!

= 27720
Prepared by [Link] 15
Permutations with Repetition
The number of permutation of ‘n’ objects taken ‘r’ at a time
with repetitions allowed is 𝒏𝒓 .
For example, the number of string of length ‘n’ can be formed
from the English alphabet = 26𝑛
Problem 1:
How many bit string of length 10 that begin and end with 1 ?
Solution:
The bits in the remaining 8 places can be filled in 28 ways, after
fixing 1 in the first and last places.
∴ No. of bit strings of length 10,start end with 1 = 28 = 256.
Prepared by [Link] 16
Problem 2:
How many 4 digit numbers can be formed using the digits 2,4,6,8
when repetition of digits is allowed?
Solution:
There are 4 ways of filling each of the digit positions.
∴ Total No. of 4-digits formed = 4×4×4×4=256
Circular Permutation
The arrangement of objects in a circle is called Circular
Permutation.
The number of arrangements of n objects in
a circle = (n-1)!

Prepared by [Link] 17
Problem 3:
Determine the number of ways in which 5 software engineers and 6 electronics
engineers can be seated around a table so that no two software engineers can sit
together.
Solution:
The 6 electronics engineers sit in a circular table in (6-1)!=5! Ways.
The 5 software engineers must be seated in between two electronics engineers so
that no two software engineers can sit together.
There are six places for software engineers.
Therefore, they can be placed in 6! different ways.
Total [Link] ways to arrange the engineers to sit on a round table = (5!)(6!)
= 86400.

Prepared by [Link] 18
Problem 4:
How many bit strings of length 10 contain (a) exactly four 1’s (b) atmost four 1’s
(c) atleast four 1’s (d )an equal number of 0’s and 1’s.

Solution:
(a) A bit string of length 10 can be considered to have 10 [Link] 10 positions
should be filled with four 1’s and six 0’s.
10!
∴ No. of required bit strings = = 210.
4!6!

(b) The 10 positions should be filled up with no 1 and ten 0’s (or) one 1 and 9
0’s(or)two 1’s and eight 0’s (or) three 1’s and seven 0’s (or) four 1’s and six 0’s.
𝟏𝟎! 𝟏𝟎! 𝟏𝟎! 𝟏𝟎! 𝟏𝟎!
Required no. of bit strings = + + + + = 386
𝟎!𝟏𝟎! 𝟏!𝟗! 𝟐!𝟖! 𝟑!𝟕! 𝟒!𝟔!

(c) The ten positions are to be filled up with four 1’s and six 0’s (or) five 1’s
and five 0’s etc (or) ten 1’s and no 0’s.
𝟏𝟎! 𝟏𝟎! 𝟏𝟎! 𝟏𝟎! 𝟏𝟎! 𝟏𝟎! 𝟏𝟎!
Required [Link] bit strings = + + + + + + = 848.
𝟒!𝟔! 𝟓!𝟓! 𝟔!𝟒! 𝟕!𝟑! 𝟖!𝟐! 𝟗!𝟏! 𝟏𝟎!𝟎!

𝟏𝟎!
(d) The ten positions are to be filled up with five 1’s and five 0’s = = 252.
𝟓!𝟓!
Prepared by [Link] 19
 Problem 5:
In how many of the permutations of 10 things taken 4 at a time will
(a) one thing always occur (b) never occur
Solution:

We can keep aside the particular thing which will always occur, the
number of permutations of 9 things taken at a time is 9P3.

Now this particular thing can take up any one of the four places and can
be arranged in 4 ways.

The no. of permutations = 9P3 × 4

= 9×8×7×4

= 2016.

If we are keeping the particular thing aside which has never to occur, the
number of 9 things

(10-1= 9) taken 4 at a time is 9p4 = 9×8×7×4 = 3026.

Prepared by [Link] 20
PROBLEMS ON COMBINATION

Prepared by [Link] 21
Problem 1:
If nC5=20 nC4, find ‘n’
Solution:
Given nC5=20 nc4
𝑛 𝑛−1 𝑛−2 𝑛−3 𝑛−4 𝑛 𝑛−1 𝑛−2 𝑛−3
⇒ =20
[Link].5 [Link]
𝑛−4
⇒ = 20
5

⇒ 𝑛 − 4 = 20 . 5
⇒ 𝑛 = 100 + 4
⇒ 𝑛 = 104

Prepared by [Link] 22
Problem 2:
In how many ways can 5 persons be selected from amongst 10 persons?
Solution:
The selection can be done in 10𝐶5 ways.
𝑛!
nCr =
𝑟! 𝑛−𝑟 !

10!
𝟏𝟎𝑪𝟓 =
5! 10−5 !

10×9×8×7×6×5!
=
5! 5!

10×9×8×7×6
= = 9×28
120

= 252 ways.

Prepared by [Link] 23
Problem 3:
A committee of 5 is to be selected from 6 boys and 5 girls. Determine the number of
ways of selecting the committee if it is to consist of atleast 1 boy and 1 girl.
Solution:
The committee may consist of
(i) 1 boy, 4 girls
(ii) 2 boys, 3 girls
(iii) 3 boys, 2 girls
(iv) 4 boys, 1 girl

The number of committees of type (i)

= 6c𝟏 × 5c𝟒 = 6×5 = 30
The number of committees of type (ii)
= 6c𝟐 × 5c𝟑 = 15×10 = 150
The number of committees of type (iii)
𝟔∗𝟓∗𝟒
= 6c𝟑 × 5c𝟐 = = 200
𝟏∗𝟐∗𝟑
The number of committees of type (iv)
= 6c𝟒 × 5c𝟏 = 15×5 = 75
The total number of ways of forming the committee
= 50+150+200+75 = 455.

Prepared by [Link] 24
Problem 4:
A committee of 3 people is to be chosen from 3 women,5 men and 4 students.
(i) How many ways can the committee be chosen?(ii)How many ways can the
committee be chosen if it cannot include both men and women?
Solution :
Total No. of people = 5+4+3 = 12
𝟏𝟐∗𝟏𝟏∗𝟏𝟎
(i) Number of ways of selecting the committee of 3 people = 12c𝟑 = = 220
𝟏∗𝟐∗𝟑

(ii) Number of ways of selecting committees of 3 people with no women = 9c𝟑

𝟗∗𝟖∗𝟕
= = 84
𝟏∗𝟐∗𝟑

𝟕∗𝟔∗𝟓
Number of ways of selecting committees of 3 people with no men = 7c𝟑 = = 35
𝟏∗𝟐∗𝟑

Number of ways of selecting committees of 3 people with students alone = 4c𝟑

𝟒∗𝟑∗𝟐
= =4
𝟏∗𝟐∗𝟑

∴ Number of ways choosing the committee that include both men and women
= 84+35-4 = 115.

Prepared by [Link] 25
Problem 5:
Suppose that there are 9 faculty members in the mathematics
department and 11 in the computer science department. How many
ways there are to select a committee to develop a discrete maths course
at a school in the committee is to consist of three faculty members
from the maths department and four from the computer science dept.
Solution:
3 educationalists can be chosen from 9 educationalists in 9C3 ways.
4 socialist can be chosen from 11 in 9C3 ways.
Therefore, by product rule, the number of ways to select the committee is

9C3 × 11C4= 84×330= 27720 ways.

Prepared by [Link] 26
Problem 6:
A box contains 6 white balls and 5 red balls . Find the number of ways 4 balls
can be drawn from the box. If
(i) They can be any colour.

(ii) Two must be white and 2 red.

(iii)They all must be of the same colour.

Solution:
(i) 4 balls of any colour can be chosen from 11 balls in 11C4 ways = 330 ways.

(ii) 2 white balls can be chosen in 6C2 ways and 2 red balls can be chosen in

5C2 ways.
No. of ways to choose 2 white and 2 red balls = 6C2 + 5C2
= 15+10 = 25 ways.
(iii) No. of ways selecting 4 balls all of the same colour is 6C4 + 5C4

= 15+5 = 20 ways.

Prepared by [Link] 27
Find the number of non-negative integer solution of the equation
x1 + x2 + x3 =11.
Solution:
Let P1 be the property that x1> 3.
Let P2 be the property that x2> 4
Let P3 be the property that x3> 6.
Now the number of solutions satisfying the inequalities
x1  3, x2  4 , x3 6 is N(P1’ P2’ P3’) .
By the principle of inclusion – exclusion we have
N(P1’ P2’ P3’) = N – N(P1) – N(P2) – N(P3) + N(P1 P2) +N(P1 P3)
+ N(P2 P3) – N(P1 P2 P3)
N = Total number of solutions = C(3+11-1,11) = 78.

Prepared by [Link] 28
 N (P1) = No. of solutions with x1 3.
= c1( 3+7-1,7) = c(9,7) = 36.
N (P2) = No. of solutions with x2 5.
= c1( 3+6-1,6) = c(8,6) = 28.
N (P3) = No. of solutions with x3 7.
= c1( 3+4-1,4) = c(6,4) = 15.
N (P1P2) = No. of solutions with x1 4 and x2 5.
= c1( 3+2-1,2) = c(4,2) = 6.
N (P1P3) = No. of solutions with x1 4 and x3 7 = 0.
N (P1P2 P3) = No. of solutions with x1 4 and x2 5 and x3 7
= 0.
N(P1’ P2’ P3’) = 78 – 36 – 28-15+6+1+0+0 = 6.
The equation x1 + x2 + x3 =11 with respect to the given constraints has 6
solutions
Prepared by [Link] 29
Combinations with Repetitions
The number of r-combinations (selection of r objects) of n kinds of objects, if
repetitions of the objects is allowed = C(n+r-1, r).
Problems :
1. Suppose that a cookie shop has four different kinds of cookies. How many
different ways can six cookies be choosen?
Solution :
No. of available cookies n = 4
No .of cookies to be selected r = 6
The number of ways to choose 6 cookies is the number of 6-combinations of a set
with four elements.
∴ No. of ways of selection = C(4+6-1,6) = C(9,6) = C(9,3) = 84.
Prepared by [Link] 30
 MODULE-II
PRINCIPLE OF INCLUSION AND EXCLUSION

Prepared by [Link] 31
This Principle is used to count the number of
elements in the union of two or more sets.

(i) If A and B are two sets, then the number of

elements in their union set (A ∪ B) is given by

|A ∪ B|=|A|+|B|-|A ∩ B| (or)

n(A ∪ B)=n(A)+n(B)-n(A ∩ B).

Prepared by [Link] 32
(ii) If A,B,C are any three sets then

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣ (or)

n(A∪B∪C)=n(A)+n(B)+n(C)-n(A∩B)-n(A∩C)-n(B∩C)+n(A∩B∩C).

(iii) If A,B,C,D are any four sets then,

|A∪B∪C∪D|=|A|+|B|+|C|+|D|-|A∩B|-|A∩C|-|A∩D|-|B∩C|-
|B∩D|-|C∩D|+|A∩B∩C|+|A∩C∩D|+|A∩B∩D|+|B∩C∩D|-
|A∩B∩C∩D|.

Prepared by [Link] 33
The Principle of Inclusion-
Exclusion
| A1  A2  . . .  An | = Σ | Ai |

- Σ | Ai  Aj |

+ Σ | Ai  Aj  Ak |

- ...

+ (-1)n-1 Σ | A1  A2  ... 

An | Prepared by [Link] 34
EXAMPLE: 1
The survey was conducted among 1000
students. 595 like DM, 565 like POM, 550 like
DSP, 395 like DM and POM, 350 like POM and
DSP, 400 like DSP and DM, & 250 like all the
three subjects.

(i) Find the number of students who like

atleast one of the subjects,

(ii) How many of them like POM and do not

like DM and DSP.

(iii) How many of them who do not like DM,

POM, DSP.
Prepared by [Link] 35
Solution:
Let D : Set of Students like DM,
P : Set of Students like POM
S : Set of Students like DSP
|U|=1000, |D|=595, |P|=565, |S|=550,
|D∩P|=395, |P∩S|=350, |D∩S|=400, |D∩P∩S|=250
i) Number of students who like atleast one of the subjects
=|D∪P∪S|.
|D∪P∪S|= |D|+|P|+|S|-|D∩P|-|P∩S|-|D∩S|+|D∩P∩S|
= 595+565+550-395-400-350+250 =815.
Prepared by [Link] 36
|D∪P∪S|= 815.
ii) n(P alone)= 565-145-250-100=70
Number of students who like POM but not DM & DSP
= 𝑃∩𝐷∩𝑆
= 𝑃 − 𝐷∩𝑃 − 𝑃∩𝑆 + 𝐷∩𝑃∩𝑆
=565-395-350+250
=70
(iii) Number of students don’t like all
= 𝑃∩𝐷∩𝑆
= 𝑈 - 𝑃∪𝐷∪𝑆
=1000-815=185.

Prepared by [Link] 37
EXAMPLE : 2
Determine the number of Integers between 1 and
250 that are not divisible by 2 , 3 or 5.

Solution:

Let A : Set of Integers between 1 and 250 are divisible by 2.

B : Set of Integers between 1 and 250 are divisible by 3.

C : Set of Integers between 1 and 250 are divisible by 5

|U| = 250

250 250 250

Therefore, |A| = = 125, |B| = = 83, |C| = = 50
2 3 5

Prepared by [Link] 38
 250 250 250 250
|AꓵB| = = = 41, |BꓵC| = = = 16
2×3 6 3×5 15

250 250 250 250

|AꓵC| = 2×5
=
10
= 25, |AꓵBꓵC| = 2×3×5
=
30
= 8.

∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

= 125+83+50+41-16-25+8 = 184

Therefore , The number of integers that are not divisible by 2 , 3 or 5

is |𝐴 ꓵ 𝐵 ꓵ 𝐶 | = |U| -∣A∪B∪C∣ = 250 -184 = 66.

Prepared by [Link] 39
EXAMPLE : 3
A survey of 150 college students reveals that 83 own
automobiles , 97 own bikes , 28 own motocycles , 53 own a car
and a bike ,14 own a car and motorcycles , 7 own a bike and a
motorcycle and 2 all three.
(i) How many students own a bike and nothing else?
(ii) How many students do not own any of the three?
Solution:

Let A : Set of students own a car or automobile.

B : Set of students own a bike .

C : Set of students own a motorcycle.

From the problem, we have the data

n(A) = 83, n(B) = 97, n(C) = 28, n(AꓵB) = 53 , n(AꓵC) = 14 ,

n(BꓵC) = 7, n(AꓵBꓵC) = 2 Prepared by [Link] 40
(i) Number of students who own a bike and
nothing else:

=|B – (AꓴC)|

=|B| - |AꓵB| - |BꓵC|+|AꓵBꓵC|

= 97 – 53 – 7 + 2 = 39

Therefore , 39 Students own only bike.

Prepared by [Link] 41
(ii) n(𝐴 ꓵ 𝐵 ꓵ 𝐶 ) = N – n(AꓴBꓴC)

Now,

n(AꓴBꓴC) = n(A) + n(B) + n(C) – n(AꓵB) – n(AꓵC) – n(BꓵC) +

n(AꓵBꓵC).

= 83 + 97 + 28 -53 -14 -7 +2

=136.

Therefore , Number of Students do not own any of the three

vehicles = 150 – 136 =14 Students.

Prepared by [Link] 42
Alternate form of principle of
inclusion and exclusion

Prepared by [Link] 43
Let N be the total number of objects.

Let A, B and C be the three characters possessed by

the objects.

Then n(A̅ ∩B̅ ∩C̅) = N-n(AᴜBᴜC)

=N-n(A)-n(B)-n(C)
+n(A∩B)+n(A∩C)+n(B∩C)-n(A∩B∩C)

Prepared by [Link] 44
EXAMPLE : 4
Using the principle of inclusion and exclusion
find the number of prime numbers not exceeding
100.
Solution:
The primes below 10 are 2,3,5,7

Therefore the number of primes not exceeding 100 is

4+N(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )

Here, 𝐴1 =Set of integers divisible by 2

𝐴2 = Set of integers divisible by 3

𝐴3 = Set of integers divisible by 5

𝐴4 = Set of integers divisible by 7

Prepared by [Link] 45
Since there are 99 possible integers >1 and not exceeding
100, by principle of inclusion and exclusion.

n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 ) = 99 - n(𝐴1 ⋃ 𝐴2 ⋃ 𝐴3 ⋃ 𝐴4 )
=99 –n(𝐴1 ) – n(𝐴2 ) – n(𝐴3 ) –n(𝐴4 ) +n(𝐴1 ⋂ 𝐴2 ) +n(𝐴1 ⋂ 𝐴3 )+n(𝐴1 ⋂
𝐴4 )+n(𝐴2 ⋂ 𝐴3 )
+ n (𝐴2 ⋂ 𝐴4 ) + n(𝐴3 ⋂ 𝐴4 ) - n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ) - n(𝐴1 ⋂ 𝐴3 ⋂ 𝐴4 )-
n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴4 ) –
n(𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )+ n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )

100 100
| 𝐴1 | = = 50; | 𝐴2 | = = 33
2 3

100 100
| 𝐴3 | = = 20 ; | 𝐴4 | = = 14
5 7

Prepared by [Link] 46
| 𝐴1 ⋂ 𝐴2 | = [100/(2*3) ]= [100/LCM(2,3)] =
[100/6] =16

| 𝐴1 ⋂ 𝐴3 | = [100/(2*5)] = [100/10 ] =10

| 𝐴1 ⋂ 𝐴4 |= [100/(2*7)] = [100/14] =7

| 𝐴2 ⋂ 𝐴3 | = [100/(3*5)] = [100/15] =6

| 𝐴2 ⋂ 𝐴4 |= [100/(3*7)] = [100/21] =4

| 𝐴3 ⋂ 𝐴4 | = [100/(5*7)] =[100/35] =3

Prepared by [Link] 47
| 𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 | = [ 100/lcm(2*3*5)]= [100/80] =3
| 𝐴1 ⋂ 𝐴2 ⋂ 𝐴4 | = [ 100/(2*3*7)] =[100/42] =2
| 𝐴1 ⋂ 𝐴3 ⋂ 𝐴4 | = [ 100/(2*5*7)] = [100/70] = 1
| 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 | = [ 100/(3*5*7)] = [100/105] =0
| 𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 | = [ 100/(2*3*5*7)] =
[100/215] = 0
| 𝐴1 ⋃ 𝐴2 ⋃ 𝐴3 ⋃ 𝐴4 |
= 50 + 33 +20 +14 - 16 - 10 - 7 - 6 - 4 - 2 + 3 + 2 + 1
+0-0
= 78

Prepared by [Link] 48
n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 ) = 99 -78 = 21

The number of primes not exceeding 100 = 4+n(𝐴1

⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )
= 4 + 21
= 25

Prepared by [Link] 49
EXAMPLE : 5
Find the number of integers between 1 and 2000
inclusive that are not divisible by 2,3,5 or 7.

Solution:

Let
𝐴1 be the set of integers that are divisible by 2
𝐴2 be the set of integers that are divisible by 3
𝐴3 be the set of integers that are divisible by 5
𝐴4 be the set of integers that are divisible by 7

Prepared by [Link] 50
To find n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 ) by principle of inclusion and
exclusion.

n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 ) =N –n(𝐴1 ) – n(𝐴2 ) – n(𝐴3 ) –n(𝐴4 ) +n(𝐴1 ⋂

𝐴2 ) +n(𝐴1 ⋂ 𝐴3 )+n(𝐴1 ⋂ 𝐴4 )+n(𝐴2 ⋂ 𝐴3 ) + n(𝐴3 ⋂ 𝐴4 ) + n (𝐴2 ⋂
𝐴4 ) - n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ) - n(𝐴1 ⋂ 𝐴3 ⋂ 𝐴4 )- n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴4 ) –
n(𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )+ n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )

Prepared by [Link] 51
 2000 2000
| 𝐴1 | = = 1000 ; | 𝐴2 | = = 666
2 3

2000 2000
| 𝐴3 | = = 400 ; | 𝐴4 | = = 285
5 7

2000 2000
| 𝐴1 ∩ 𝐴2 | = = 333 ; | 𝐴1 ∩ 𝐴3 | = = 200
2×3 2×5

2000
| 𝐴1 ∩ 𝐴4 | = = 143
2×7

2000
| 𝐴2 ∩ 𝐴3 | = = 133
3×5

Prepared by [Link] 52
 2000 2000
| 𝐴2 ∩ 𝐴4 | = = 95 ; | 𝐴3 ∩ 𝐴4 | = =57
3×7 5×7

2000 2000
| 𝐴1 ∩ 𝐴2 ∩ 𝐴3 | = = 66 ; | 𝐴1 ∩ 𝐴2 ∩ 𝐴4 | = =47
2𝑋3𝑋5 2𝑋3𝑋7

2000 2000
| 𝐴1 ∩ 𝐴3 ∩ 𝐴4 | = = = 28 ; | 𝐴2 ∩ 𝐴 3 ∩ 𝐴4 | = = = 19
2𝑋5𝑋7 3𝑋5𝑋7

2000
| 𝐴1 ∩ 𝐴2 ∩ 𝐴3 ∩ 𝐴4 | = = =9
2𝑋3𝑋5𝑋7

n(𝐴1 ⋂ 𝐴2 ⋂ 𝐴3 ⋂ 𝐴4 )

= 2000 - 1000 - 666 - 400 - 285 + 333 + 200 + 143 + 133 + 95 +

57 - 66 - 47 - 28 - 19 + 9

= 458.

Prepared by [Link] 53
Prepared by [Link] 54
Prepared by [Link] 55
Prepared by [Link] 56
If m pigeons are accommodated in n pigeonholes and m > n then one of the
𝒎−𝟏
pigeonholes must contain atleast + 𝟏 pigeons.
𝒏

Note: [x] denotes the greatest integer less than or equal to x.

Pigeonhole principle:

If (n+1) pigeon occupies ‘n’ holes then at least one hole has more than one
pigeon.

Note:

If kn+1 or more pigeons occupy k pigeonholes,there will be more than n

pigeons in atleast one pigeonholes where n is a positive integer.

The pigeonhole principle is also called as Dirichlet drawer principle.

Prepared by [Link] 57
 What is the minimum number of students required in a Discrete
mathematics class to be sure that at least six will receive the
same grade if there are five possible grades A,B,C,D & E?
Solution:
Number of pigeonholes = Number of grades
i.e. n = 5
Since atleast six students (pigeons) to receive the same grade in
Discrete mathematics class
k+1 = 6
k=5
 The smallest integer N = kn+1 = 5.5 + 1 = 26.
Hence, minimum no. of students = 26.

Prepared by [Link] 58
Show that 102 students must be in a class to guarantee that at
least two students receive the same score on the final exam if the
exam is graded on a scale from 0 to 100 points?
Solution:
Given exam is graded on a scale from 0 to 100.
Therefore there are 101 possible scores(Pigeonholes). i.e., n = 101
Since atleast two students (pigeons) to receive the same score on
the final exam
k+1 = 2 k=1
 The smallest integer N = kn+1 = 1×101 + 1 = 102.
By Pigeonhole principle we have among 102 students there must
be atleast two students with the same score.
The class should contain minimum 102 students.

Prepared by [Link] 59
If seven colours are used to paint 50 bicycles then show that at least
8 bicycles will be of the same colour.

Solution:

Here Number of pigeon = m = Number of bicycles = 50

Number of holes = n = Number of colours = 7

By Pigeon hole principle, we have

𝒎−𝟏 𝟓𝟎 − 𝟏
+𝟏= +𝟏=𝟖
𝒏 𝟕
Therefore, atleast 8 bicylces will be of the same colour.

Prepared by [Link] 60
If we select any group of 1000 students on campus, show that at least three
of them must have same birthday?

Solution:

The maximum number of days in a year = 366.

Here Number of students = Number of pigeons = m = 1000

Number of days in a year = Number of holes = n = 366

By Generalized Pigeon hole principle,

Minimum number of students having same birthday is

𝒎−𝟏 𝟏𝟎𝟎𝟎−𝟏
+𝟏= + 𝟏 = 𝟐 + 𝟏 = 𝟑.
𝒏 𝟑𝟔𝟔

Hence at least 3 must have same birthday.

Prepared by [Link] 61
Prove that an equilateral triangle; whose sides are of length 1 unit, if any five
points are chosen, then at least two of them lies in a triangle whose sides
apart is less than ½.

Solution:

Let D,E and F are mid points of the side AB,BC and AC respectively. So
that the triangle ABC divided into four equilateral triangles of each side
½.

Now Number of pigeon = Number of interior points = 5

Number of pigeon holes = Number of triangles = 4

By Pigeonhole principle, at least one triangle has more than 1 point.

Since each triangle side is ½ the distance between two interior points of
any sub triangle is less than ½.

Prepared by [Link] 62
Prepared by [Link] 63
If n pigeon holes are occupied by (kn+1) pegeons, k is a positivie integer, prove
that at least one pigeon hole is occupied by (k+1) or more pigeons. Hence find the
minimum number of m integers to be selected from S= 1,2,….9 so that the sum
of two of the m integers are even.
Solution:
Assume n holes are occupied by (kn+1) pigeons.
Claim: At least one hole is occupied by (k+1) or more pigeon.
If not, (ie) At least one hole is not occupied by (k+1) or more pigeon.
 Each hole contains at most k pigeons.
Since we have n holes the total number of pigeon is at most kn.
which is a contradiction
 at least one hole is occupied by (k+1) or more pigeon.
Let us divide set S = 1, 2,…9 in to two subsets 1,3,5,7,9 and 2,4,6,8
which may be treated as pigeon holes.
n = 2.
At least two numbers must be chosen either from the first subset or from
the second.
(ie) at least one pigeon hole contain two pigeons.
(ie) k+1 =2  k = 1
The minimum number of the pigeon required or minimum number of
integers to be selected is equal to kn+1 = 3.

Prepared by [Link] 64
Mathematical Induction

Prepared by [Link] 65
Prepared by [Link] 66
Problem 1:
Prove by mathematical induction for n, a positive integer,
𝒏 𝒏+𝟏 (𝟐𝒏+𝟏)
12 + 22 + …. + n2 =
𝟔
Solution :

𝒏 𝒏+𝟏 (𝟐𝒏+𝟏)
Let p(n) : 12 + 22 + ….+ n2 =
𝟔

To Prove: P(1) is true.

𝟏 𝟏+𝟏 (𝟐.𝟏+𝟏)
P(1) : 12 = = 1 is true.
𝟔

Assume that P(k) is true

𝒌 𝒌+𝟏 (𝟐𝒌+𝟏)
i.e., P(k) : 12 + 22 + ….+ k2 = -------(1) is
𝟔
true,
where k is any integer.
Prepared by [Link] 67
 Claim : P(k+1) is true.

i.e., to prove P (k+1) : 12 + 22 + ….+ k2 + (k+1)2 = (𝑘+1) 𝑘+1)+1 (2 𝑘+1 +1)

6

𝑘 𝑘+1 (2𝑘+1)
Consider 12 + 22 + ….+ k2 + (k+1)2 = + (k+1)2 using (1)
6

𝑘+1 [𝑘 2𝑘+1 +6 𝑘+1 ]

=
6

(𝑘+1) 𝑘+2 (2𝑘+3)

=
6

(𝑘+1) 𝑘+1)+1 (2 𝑘+1 +1)

=
6

 P(k+1) is true.
Hence by mathematical induction, for any n>0,
𝑛 𝑛+1 (2𝑛+1)
12 + 22 + ….+ n2 =
6 Prepared by [Link] 68
Problem 2:
By mathematical induction show that 1 +2 + 22 + ----+ 2n = 2n+1 – 1
for n≥ 𝟏.
Solution:
Let P(n) : 1 +2 + 22 + ----+ 2n = 2n+1 – 1
To prove: P(1) is true
P (1) : 21 = 21 – 1 = 1 is true.
Assume that P(k) :1 +2 + 22 + ----+ 2k = 2k+1 – 1 is true
Claim: P(k+1) is true.
P(k+1) = 1+2+22+…..+2k + 2k+1
= 2k+1 – 1+ 2k+1 = 2.2k+1 -1 = 2k+2 -1 = 2(k+1)+1 -1
 P(k+1) is also true.
Hence the proof. Prepared by [Link] 69
Problem 3:
By using mathematical induction, show that n  2n+1 , n = 5,6,7,….
Solution :
Let p(n) : n  2n+1
To prove: p(5) is true: p(5) : 5  25+1 is true.
Assume that p(k) : k  2k+1 is true ----I
Claim: p(k+1) is true.
Using (1), k  2k+1 is true
Multiply on both sides by 2 we get

2(k!)  2. 2k+1 ⇒ 2(k!)  2k+2

⇒ (k+1) k!  2(k!)  2k+2 [By (*)]
⇒ (k+1) k!  2k+2 ⇒ (k+1)! . 2k+2

[since (k+1)  2 ⇒ (k+1) k!  2 k! -------(*) {because k >5}]

Therefore p(k+1) is true. Hence n! by[Link]
Prepared
n+1
70
Problem 4: Prove by mathematical induction that for all n1 ,n3 +2n
is a multiple of 3.
Solution:
Let P(n) : n3 +2n is a multiple of 3.
(i) To Prove: P(1) is true
P(1) :13 +2.1 = 3 which is a multiple of 3.
(ii) Assume that P(k) is true. i.e., P(k) : k3 +2k is a multiple of 3 --(1)
Claim : To Prove: P(k+1) is true.
Consider (k+1)3 + 2(k+1)
= k3 + 3k2 +3k+2k+3
= (k3 +2k) + 3(k2 + k+1) ------- (2)
Since k3 + 2k is a multiple of 3, (2) is also a multiple of 3.
By the Principle of Mathematical
Prepared byinduction,
[Link] the proof follows 71
Problem 5: Using Mathematical induction show that n3- n is divisible by 3 for n ∈Z+.
Solution:
Let P (n) = n3- n is divisible by 3.
To Prove: P(1) is true:
P(1) : 13- 1 is divisible by 3 is true.
Assume that P(k) : k3- k is divisible by 3 ---(1)
Claim: P(k+1) is true.
P(k+1) = (k+1)3- (k+1)
= (k3- k) + 3(k2 +k) -------(2)
 k3 - k is divisible by 3 and 3(k2 +k) is divisible by 3, we have equation (2) is
divisible by 3.
P(k+1) is true.
By the principle of Mathematical induction n3- n is divisible by 3

Prepared by [Link] 72
Problem 6:
Prove by induction that 2n3 + 3n2 + n is divisible by 6 for all integers n ≥ 0.
Solution:
Let P(n) be the statement 2n3 + 3n2 + n is divisible by 6.
To prove: P(n) is true " n  0.
Basis step: To prove P(0) is true [Here n0 = 0]

 P(0): 0 is divisible by 6, which is true

So, P(0) is true
Inductive step: Assume P(k) is true, k > 0.

 2k3 + 3k2 + k is divisible by 6 is true

2k3 + 3k2 + k = 6x --------- (1)

where x is an integer.

Prepared by [Link] 73
To prove: P(k + 1) is true.
That is to prove 2(k + 1)3 + 3(k + 1)2 + (k + 1) is divisible by 6 is
true. Now
2(k + 1)3 + 3(k + 1)2 + (k + 1) = 2(k3 + 3k 2 + 3k + 1) + 3(k 2 + 2k + 1) + k + 1

= (2k3 + 3k 2 + k ) + 6k 2 + 6k + 2 + 6k + 3 + 1

= (2k3 + 3k 2 + k ) + 6k 2 + 12k + 6

= 6x + 6(k 2 + 2k + 1) [using(1)]
= 6[x + k 2 + 2k + 1],

where x + k 2 + 2k + 7 is an integer.
 P(k + 1) is true.
Thus P(k) is true  P(k + 1) is true.
Hence by first principle of induction P(n) is true " n  0.

Prepared by [Link] 74
Problem 7:

If the sum of the cubes of three consecutive integers is a cube k3 prove that 3 | k.
Solution:
Let n, n + 1, n + 2 be the three consecutive integers.

Given n3 + (n + 1)3 + (n + 2)3 is a cube k3

n3 + n3 + 3n2 + 3n + 1+ n3 + 3n2 · 2 + 3n · 22 + 23 = k3

3n3 + 9n2 + 15n + 9 = k3

3(n3 + 3n2 + 5n + 3) = k3

3 | k3 → 3 | k · k · k

Since 3 is a prime, 3 | k.

Prepared by [Link] 75
Problem 8:
1 1 1 1 𝑛
Prove by induction + + +…….+ =
1.3 3.5 5.7 (2𝑛−1)(2𝑛+1) (2𝑛+1)
Solution:
Prepared by [Link] 77
Prepared by [Link] 78
Problem 9:
Prove that for all n ≥ 6, 4𝑛 < 𝑛2 -7
Solution:

Prepared by [Link] 79
Prepared by [Link] 80
Problem 10:
Prove that for all n ≥ 4, 2𝑛 < 𝑛! 𝑏𝑦 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛
Solution:

Prepared by [Link] 81
Prepared by [Link] 82
Problem 11:
Prove 𝑏𝑦 𝑖𝑛𝑑𝑢𝑐𝑡𝑖𝑜𝑛 13𝑛 − 6𝑛 𝑖𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑏𝑦 7.
Solution:

Prepared by [Link] 83
Prepared by [Link] 84
Prepared by [Link] 85
Prepared by [Link] 86
Prepared by [Link] 87
Prepared by [Link] 88
Prepared by [Link] 89
Prepared by [Link] 90
Prepared by [Link] 91
Prepared by [Link] 92
Prepared by [Link] 93
Prepared by [Link] 94
Prepared by [Link] 95
Prepared by [Link] 96
Prepared by [Link] 97
Prepared by [Link] 98
Prepared by [Link] 99
 RECURRENCE RELATION
Formation of Recurrence Relation

Problems :
[Link] the recurrence relation from 𝑺 𝒌 = 𝟓 ∗ 𝟐𝒌 , 𝒌 > 𝟎.
Solution :
If 𝑘 > 1, 𝑆 𝑘 = 5 ∗ 2𝑘
= 2 ∗ 5 ∗ 2𝑘−1
=2∗𝑆 𝑘−1
The recurrence relation is 𝑆 𝑘 − 2𝑆 𝑘 − 1 = 0 and the initial condition
𝑆 0 = 5.

PREPARED BY [Link] 100

2. Find the recurrence relation for the Fibonacci sequence of
numbers.
Solution :
The sequence of numbers
0,1,1,2,3,5,8,13…… is the Fibonacci sequence of numbers.
If 𝑭𝒏 is the n-th term, then 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 , 𝑛 ≥ 2

The recurrence relation is 𝐹𝑛 − 𝐹𝑛−1 − 𝐹𝑛−2 = 0 , 𝑛 ≥ 2

with initial conditions 𝐹0 = 0, 𝐹1 = 1.

PREPARED BY [Link] 101

3. Form the recurrence relation from 𝐒 𝐤 = 𝟐𝐤 + 𝟗.
Solution :
S k = 2k + 9
S k − 1 = 2(k − 1) + 9
S k−1 =2 k +9−2
⟹𝑆 𝑘−1 =𝑆 𝑘 −2
∴ The recurrence relation 𝒊𝒔 𝑆 𝑘 − 𝑆 𝑘 − 1 = 2.

PREPARED BY [Link] 102

4. Find the recurrence relation satisfying the equation Yn = A(3)n + B(-4)n
Solution :
Given Yn = A(3)n + B(-4)n ---------(1)
Yn+1 = A3n+1 + B(-4)n+1
= 3A3n - 4 B(-4)n ---------(2)
Yn+2 = 9A3n + 16 B(-4)n ------------(3)
(3) + (2) – (1) x 12 ⇒
Yn+2 + Yn+1 - 12 Yn = 9A3n + 16 B(-4)n +3A3n - 4 B(-4)n - 12[A(3)n + B(-
4)n] = 0
Yn+2 + Yn+1 - 12Yn = 0 which is the required solution.

PREPARED BY [Link] 103

PREPARED BY [Link] 104
PREPARED BY [Link] 105
PREPARED BY [Link] 106
Recurrence relation

If {𝒂𝒏 }, n ≥ 0 represents a sequence of numbers then an

expression that relates a term of the sequence to one or
more of its preceeding terms is called a recurrence
relation.
For example , 𝒂𝒏+𝟐 = 𝒂𝒏+𝟏 + 𝟐𝒂𝒏 is a recurrence relation.
𝑭𝒏 = 𝑭𝒏−𝟏 + 𝑭𝒏−𝟐 , 𝒏 ≥ 𝟐 is called the Fibonacci
recurrence relation for the sequence of numbers
{1,1,2,3,5,8,13,…..}.

PREPARED BY [Link] 107

Order of recurrence relation
Order of a recurrence relation = Highest subscript –
lowest subscript.
𝒊 𝑭𝒏 − 𝑭𝒏−𝟏− 𝑭𝒏−𝟐= 𝟎 is a recurrence relation of order
𝒏− 𝒏−𝟐 = 2
(ii) 𝟐𝒂𝒏 − 𝒂𝒏−𝟏 = 𝟓 ∗ 𝟐𝒏 is a recurrence relation of order
𝒏 − 𝒏 − 𝟏 = 𝟏.

PREPARED BY [Link] 108

General form of k-th order recurrence relation

Consider 𝐜𝟎 𝒚𝒏+𝒌 + 𝒄𝟏 𝒚𝒏+𝒌−𝟏 + 𝒄𝟐 𝒚𝒏+𝒌−𝟐 + ⋯ . +𝒄𝒏 𝒚𝒏 = 𝒇(𝒏)

is the general form of the k-th order recurrence relation ,where

𝒄𝟏 , 𝒄𝟐 ,……… 𝒄𝒏 are constants and 𝒇(𝒏) is a function of ‘n’ only.

This recurrence relation is non-homogeneous type. When

𝒇 𝒏 = 𝟎, the recurrence relation is said to be homogeneous.

PREPARED BY [Link] 109

Solution of Recurrence
Relation Using Generating
Function

PREPARED BY [Link] 110

Solution of Recurrence Relation Using
Generating Function
We first introduce the concept generating functions and
then we will consider how generating function is used to solve a
recurrence relation.

Generating Function
Let 𝒂𝟎, 𝒂𝟏 , 𝒂𝟐 ,………. be a sequence of real numbers.
The function 𝒇 𝒙 = 𝒂𝟎 + 𝒂𝟏 𝒙 + 𝒂𝟐 𝒙𝟐 +……… = 𝒊=𝟎 𝒂𝒊 𝒙
𝒊
is
called the generating function for the given sequence .
For example, (𝟏 − 𝒙)𝒏 is the generating function of the sequence
𝒎
, 0 ≤ r ≤ n. PREPARED BY [Link] 111
𝒓
PREPARED BY [Link] 112
 Some useful Expansion:

∞ 𝒏 ∞
1. 𝒏=𝟎 𝒙 = (𝟏 − 𝒙)−𝟏 2. 𝒏 𝒏
𝒏=𝟎(−𝟏) 𝒙 = (𝟏 + 𝒙)−𝟏

∞ 𝒏 𝒏 ∞
3. 𝒏=𝟎 𝒂 𝒙 = (𝟏 − 𝒂𝒙)−𝟏 4. 𝒏 𝒏 𝒏
𝒏=𝟎(−𝟏) 𝒂 𝒙 =

(𝟏 + 𝒂𝒙)−𝟏

∞ ∞ (𝒏+𝟏)(𝒏+𝟏) 𝒏
5. 𝒏=𝟎(𝒏 + 𝟏)𝒙𝒏 = (𝟏 − 𝒙)−𝟐 6. 𝒏=𝟎 𝒙 =
𝟐

(𝟏 − 𝒙)−𝟑

PREPARED BY [Link] 113

PREPARED BY [Link] 114
PREPARED BY [Link] 115
Example 1:
Solve the recurrence relation 𝒂𝒏 - 7 𝒂𝒏−𝟏 + 10 𝒂𝒏−𝟐 = 𝟎 by the method of generating
functions
with the initial condition 𝒂𝟎 = 𝟑 and 𝒂𝟏 = 𝟑 .

Solution :
Let 𝒂𝒏 -7 𝒂𝒏−𝟏 +10 𝒂𝒏−𝟐 =𝟎 , 𝒏 ≥ 𝟐 and 𝒂𝟎 = 𝟑, 𝒂𝟏 = 𝟑 .

Multiplying (1) by 𝒙𝒏 and summing from n=2 to ∞,

∞ 𝒏 ∞ ∞
𝒏=𝟐 𝒂𝒏 𝒙 -7 𝒏=𝟐 𝒂𝒏−𝟏 𝒙𝒏 +1𝟎 𝒏=𝟐 𝒂𝒏−𝟐 𝒙
𝒏
=0
∞ 𝒏
Let G(x)= 𝒏=𝟎 𝒂𝒏 𝒙

Therefore,
[𝑮 𝒙 − 𝒂𝟎 − 𝒂𝟏 𝒙] - 7 𝒙 [ 𝑮 𝒙 − 𝒂𝟎 ] + 𝟏𝟎 𝒙𝟐 𝑮 𝒙 = 0
[𝑮 𝒙 − 𝟑 − 𝟑𝒙] - 7 𝒙[ 𝑮 𝒙 − 𝟑] + 𝟏𝟎 𝒙𝟐 𝑮 𝒙 =0
𝑮 𝒙 [ 𝟏 − 𝟕𝒙 + 𝟏𝟎𝒙𝟐 ] = 𝟑 + 𝟑𝒙-21 𝒙

PREPARED BY [Link] 116

(1-2𝑥)(1-5𝑥) 𝐺 𝑥 = 3-18 𝑥
3−18 𝑥
𝐺 𝑥 =
(1−2 𝑥 )(1−5𝑥 )

Using Partial Fraction Method,

3−18 𝑥 A B
= + ----------------------*
(1−2𝑥 )(1−5𝑥 ) 1−2𝑥 1−5𝑥
3−18 𝑥 =A (1−5𝑥) + B(1−2𝑥)
1
Put 𝑥 = , Then A = 4
2
1
Put 𝑥 = , Then B = −1
5
Put A,B values in *,we get
3−18 𝑥 4 1
= -
(1−2𝑥 )(1−5𝑥 ) 1−2𝑥 1−5𝑥

PREPARED BY [Link] 117

𝐺 𝑥 = 4 (1 − 2𝑥)−1 − (1 − 5𝑥)−1

∞ 𝒏 ∞ 𝑛 𝑛 ∞ 𝑛 𝑛
𝒏=𝟎 𝒂𝒏 𝒙 = 4 𝑛=0 2 𝑥 − 𝑛=0 5 𝑥

∞ 𝑛
= 𝑛=0[4(2 ) − 5𝑛 ]𝑥 𝑛

𝒂𝒏 = 4(2𝑛 ) − 5𝑛 is the required solution.

PREPARED BY [Link] 118

 Solve the recurrence relation 𝒂𝒏+𝟐-5 𝒂𝒏+𝟏+ 𝟔𝒂𝒏=𝟐, 𝒏 ≥ 𝟎 by the
method of generating functions with the initial condition 𝒂𝟎 = 𝟏
and 𝒂𝟏 = 𝟐 .
Solution:

Given 𝒂𝒏+𝟐 -5 𝒂𝒏+𝟏 + 𝟔𝒂𝒏 =𝟐, 𝒏 ≥ 𝟎---------------(1)

Multiplying (1) by 𝒙𝒏 and summing from n=0 to ∞,

∞ 𝒏 ∞ ∞ ∞
𝒏=𝟎 𝒂𝒏+𝟐 𝒙 -5 𝒏=𝟎 𝒂𝒏+𝟏 𝒙𝒏 +6 𝒏=𝟎 𝒂𝒏 𝒙
𝒏
=2 𝒏=𝟎 𝒙
𝒏

∞ 𝒏
Let G(x)= 𝒏=𝟎 𝒂𝒏 𝒙
𝑮 𝒙 −𝒂𝟎 −𝒂𝟏 𝒙 𝑮 𝒙 −𝒂𝟎 𝟐
Therefore, − 5 + 6𝑮 𝒙 =
𝒙𝟐 𝒙 𝟏−𝒙

𝟐 𝟐𝒙𝟐
Therefore 𝑮 𝒙 − 𝒂𝟎 − 𝒂𝟏 𝒙 − 𝟓𝐱[𝐆 𝐱 − 𝒂𝟎 ]+ 6𝒙 𝑮 𝒙 =
𝟏−𝒙

Using 𝑎0 =1, 𝑎1 =2, PREPARED BY [Link] 119

Therefore 𝑮 𝒙 − 𝟏 − 𝟐𝒙 − 𝟓𝐱[𝐆 𝐱 −1]+ 6𝒙𝟐 𝑮 𝒙 =
𝟐𝒙𝟐
𝟏−𝒙

𝟐 𝟐𝐱 𝟐
𝐆 𝐱 [1-5𝒙+6 𝐱 ]-1-2𝒙 + 𝟓𝒙 =
𝟏−𝐱
𝟐 𝟐𝐱 𝟐
𝐆 𝐱 [1-5𝒙+6 𝐱 ] = +1-3𝒙
𝟏−𝐱
𝟐𝐱 𝟐 +(𝟏−𝟒𝒙+𝟑𝐱 𝟐 )
=
𝟏−𝐱
𝟏−𝟒𝒙+𝟓𝐱 𝟐
𝐆 𝐱 [(1-2𝒙)(𝟏 − 𝟑𝒙)]=
𝟏−𝐱
𝟏−𝟒𝒙+𝟓𝐱 𝟐
𝐆 𝐱 =
(1−2𝒙)(𝟏−𝟑𝒙)(𝟏−𝐱)
𝟓𝐱 𝟐 −𝟒𝒙+𝟏 𝑨 𝑩 𝑪
Let = + + [Using Partial
(1−2𝒙)(𝟏−𝟑𝒙)(𝟏−𝐱) 𝟏−𝒙 𝟏−𝟐𝒙 𝟏−𝟑𝒙
Fraction method]

𝟓𝒙𝟐 − 𝟒𝒙 + 𝟏 = 𝐀 𝟏 − 𝟑𝒙 (𝟏 − 𝟐𝒙) + 𝑩 (𝟏 − 𝒙) 𝟏 − 𝟑𝒙 + +
C 𝟏 − 𝒙 (𝟏 − 𝟐𝒙)------------*

PREPARED BY [Link] 120

Put 𝐱=1. Then A=1. Put 𝐱=1/[Link] B=-1. Put
𝐱=1/[Link] C=1
Substitute A,B,C values in *,
we get

𝟓𝐱 𝟐 −𝟒𝒙+𝟏 𝟏 𝟏 𝟏
= - +
(1−2𝒙)(𝟏−𝟑𝒙)(𝟏−𝐱) 𝟏−𝒙 𝟏−𝟐𝒙 𝟏−𝟑𝒙

𝐆 𝐱 = (𝟏 − 𝐱)−𝟏 - (𝟏 − 𝟐𝐱)−𝟏 + (𝟏 − 𝟑𝐱)−𝟏

∞ 𝐧 ∞ 𝐧 𝐧 ∞ 𝐧
∞
𝐧=𝟎 𝒂𝒏 𝐱 𝐧
= 𝐧=𝟎 𝟏𝐱 - 𝐧=𝟎 𝟐 𝐱 + 𝐧=𝟎 𝟑 𝐱𝐧
∞
= 𝐧=𝟎(𝟏 − 𝟐𝐧 + 𝟑𝐧 )𝐱 𝐧

◦ 𝐚𝐧 =𝟏 − 𝟐𝐧 + 𝟑𝐧 is the required solution.

PREPARED BY [Link] 121
Solve the recurrence relation 𝒂𝒏+𝟐-2 𝒂𝒏+𝟏+ 𝒂𝒏=𝟐𝒏, 𝒏 ≥ 𝟎 by
the method of generating functions with the initial condition
𝒂𝟎 = 𝟐 and 𝒂𝟏 = 𝟏 .

Solution:

Given 𝒂𝒏+𝟐 -2 𝒂𝒏+𝟏 + 𝒂𝒏 =𝟐𝒏 ---------------- (1)

Multiply (1) by 𝒙𝒏 and summing from 𝒏 = 𝟎 𝒕𝒐 ∞,
∞ 𝒏 ∞ ∞
𝒂
𝒏=𝟎 𝒏+𝟐 𝒙 -2 𝒏=𝟎 𝒂𝒏+𝟏 𝒙𝒏 + 𝒂
𝒏=𝟎 𝒏 𝒙𝒏
=
∞ 𝒏 𝒏
𝒏=𝟎 𝟐 𝒙
∞ 𝒏
Let G(x)= 𝒂
𝒏=𝟎 𝒏 𝒙

PREPARED BY [Link] 122

𝑮 𝒙 − 𝒂𝟎 − 𝒂𝟏𝒙 𝑮 𝒙 − 𝒂𝟎 𝟏
−2 +𝑮 𝒙 =
𝒙𝟐 𝒙 𝟏 − 𝟐𝒙

𝟐 𝒙𝟐
𝑮 𝒙 − 𝒂𝟎 − 𝒂𝟏 𝒙-2 𝒙 [𝑮 𝒙 − 𝒂𝟎 ]+ 𝒙 𝑮 𝒙 =
𝟏−𝟐𝒙

𝟐 𝒙𝟐
𝑮 𝒙 [1-2 𝒙+ 𝒙 ]-2-𝒙+4 𝒙 =
𝟏−𝟐𝒙

𝟐 𝒙𝟐
𝑮 𝒙 (𝟏 − 𝒙) = +2-𝟑𝒙
𝟏−𝟐𝒙

𝒙𝟐 +(𝟏−𝟐𝒙)(𝟐−𝟑𝒙)
=
𝟏−𝟐𝒙

𝟕𝒙𝟐 −𝟕𝒙+𝟐
𝑮 𝒙 =
(𝟏−𝒙)𝟐 (𝟏−𝟐𝒙)

PREPARED BY [Link] 123

 Using Partial Fraction method,

𝟕𝒙𝟐 −𝟕𝒙+𝟐 𝑨 𝑩 𝑪
= + +
(𝟏−𝒙)𝟐 (𝟏−𝟐𝒙) 𝟏−𝒙 (𝟏−𝒙)𝟐 (𝟏−𝟐𝒙)

𝟕𝒙𝟐 − 𝟕𝒙 + 𝟐 = 𝐀 𝟏 − 𝒙 (𝟏 − 𝟐𝒙) + 𝑩 (𝟏 − 𝟐𝒙)+C

(𝟏 − 𝒙)𝟐 ----------------*

Put 𝒙=[Link] B=-2

Put 𝒙=1/2,Then C=1

Now Equating the co-eff of constants,

2=A+B+C, 2=A-2+1, Therefore A=3

PREPARED BY [Link] 124
Substitute A,B,C values in ∗, we get

𝟕𝒙𝟐 −𝟕𝒙+𝟐 𝟑 𝟐 𝟏
= - +
(𝟏−𝒙)𝟐 (𝟏−𝟐𝒙) 𝟏−𝒙 (𝟏−𝒙)𝟐 (𝟏−𝟐𝒙)

𝑮 𝒙 =3 (𝟏 − 𝒙)−𝟏 -2 (𝟏 − 𝒙)−𝟐 + (𝟏 − 𝟐𝒙)−𝟏

∞ 𝒏 ∞ 𝒏 ∞ ∞
𝒏=𝟎 𝒂𝒏 𝒙 = 𝒏=𝟎 𝟑𝒙 -2 𝒏=𝟎(𝒏 + 𝟏)𝒙𝒏 + 𝒏=𝟎 𝟐
𝒏 𝒙𝒏
∞
= 𝒏=𝟎(𝟑 − 𝟐 𝒏 + 𝟏 + 𝟐𝒏 )𝒙𝒏
∞
= 𝒏=𝟎(𝟏 − 𝟐𝒏 + 𝟐𝒏 )𝒙𝒏

◦ 𝒂𝒏 =𝟏 − 𝟐𝒏 + 𝟐𝒏 is the required solution.

PREPARED BY [Link] 125

Example 4:
Solve the recurrence relation 𝒂𝒏 = 𝒂𝒏−𝟏 = 2n , 𝒏 ≥ 1 by the
method of generating functions with the initial condition 𝒂𝟎= 𝟎 .
Solution:

PREPARED BY [Link] 126

PREPARED BY [Link] 127
Example : 5
Solve the recurrence relation 𝒂𝒏 = 𝒂𝒏−𝟏 + (n – 1), 𝒏 ≥ 2 by
the method of generating functions with the initial condition
𝒂𝟏 = 𝟎 .

PREPARED BY [Link] 128

PREPARED BY [Link] 129
PREPARED BY [Link] 130
PREPARED BY [Link] 131
PREPARED BY [Link] 132