UNIT – III :: COMBINATORICS AND RECURRENCE RELATIONS

PART – 1 :: COMBINATORICS

Introduction:- Combinatorics is the study of arrangement of objects. Counting of objects

with certain properties is an important part of Combinatorics. To solve many different types
of problems, we must count the objects. Main counting problems can be phrased in terms of
ordered or unordered arrangement so of the objects of a set. These arrangements are called
permutations and combinations.

Basic Counting Principles :- In order to solve a counting problems, We use the following
two basic counting principles. (i) Product rule (ii) Sum rule

Product Rule :- The product rule states that if a procedure can be broken down into a
sequence of two tasks such that the first task can be done in ‘n’ ways and the second task
can be done in ‘m’ ways after the first task has been done, then there are ‘n.m’ ways of
carrying out the procedure.

Sum Rule :- According to the sum rule, if a procedure can be broken down into a sequence
of two tasks such that the first task can be done in ‘n’ ways and the second task can be done
in ‘m’ ways and if these tasks cannot be done at the same time, then there are ‘n+m’ ways
of doing one of these tasks.

Q1] There are 150 Mathematics major students and 200 Computer Science major students
at a college.
(i) How many ways are there to select two representatives so that one is a
Mathematics major and the other is a computer science major?
(ii) How many ways are there to pick one representative who is either a
Mathematics major or a Computer Science major?
Solution: Number of Mathematics Major students = 150. => n(M) = 150
Number of Computer Science major students = 200. => n(C) = 200
(i) The number of ways of selecting one representative who is a Mathematics major =
150.
By the product rule, the number of ways of selecting one representative who is a
computer science major after selecting a student who is a mathematics major is
150X200 = 30,000.
(ii) The number of ways of selecting one representative who is a mathematics major =
150.
The number of ways of selecting one representative who is a computer science
major = 200.
Hence, by the sum rule, the number of ways of selecting one representative who is
either a mathematics major or a computer science major = 150 + 200 = 350.

Permutations :- An ordered arrangement of objects from a set of distinct objects is called a

Permutation. An ordered arrangement of ‘r’ elements of a set is called an ‘r – permutations’.
The number of ‘r – permutations’ of a set with ‘n’ elements is denoted by ( n , r )∨nPr , where
n!
r≤n P(n , r ) or n Pr = .
and defined by (n−r )!
Note :- (i) n !=1.2.3 … … .. ( n−1 ) . n∨n . ( n−1 ) . ( n−2 ) … … … .3 .2 .1.
 ii) n !=n . ( n−1 ) !∨n . ( n−1 ) . ( n−2 ) !∨n . ( n−1 ) . ( n−2 ) . ( n−3 ) !
iii) 1! = 1 and 0! = 1
iv) ¿−1)! Does not exist.

Ex. 5! = 5.4.3.2.1 = 120; 5! = 5.4! i.e., 5! = 5. (4.3.2.1)=5.4! = 120.

Q2] Find (i) P(n, 0) (ii) P(n, 1) (iii) P(n, n) (iv) P(n, n-1).

n! n!
P(n, 0) or n P 0= .= =1
Solution: (i) (n−0)! n !
n! n. (n−1) !
P(n, 1) or n P1 = .= =n.
ii) (n−1)! (n−1) !
n! n. ! n !
P(n, n) or n P n= .= = =n !.
iii) (n−n)! 0 ! 1
n! n! n! n!
P(n, n−1) or n Pn−1 = .= = = =n !.
iv) (n−(n−1))! (n−n+1) ! 1 ! 1

Q3] Find the number of 5 – permutations of a set with nine elements.

Answer: The number of 5 – permutations of a set with nine elements =

9 9! 9 ! 9.8.7.6.5.4!
P5 = = = =9.8.7.6.5=15 ,120.
(9−5) ! 4! 4!
Q4] List all the permutations of { a , b , c } .

Answer: All possible permutations of the objects of set { a , b , c } may be written as

abc , acb , bac ,bca ,cab , cba .

Q5] How many possibilities are there to select a first-prize winner, a second prize winner
and a third prize winner from 50 different people who have entered a contest?

Answer: Since it is a matter of which person wins which prize, the number of ways to select
the three prize winners is the number of 3 – permutations of a set of 50 elements.
Therefore, the required possibilities may be represented as
50 50 ! 50 ! 50 . 49 . 48 . 47 !
P3 = = = =50 . 49 . 48=1 , 17 , 600
(50−3 )! 47 ! 47 ! .
n n n n 2n
Q6] Find ‘n’ if (i) P2 =72. (ii) P4 =42. P2 . (iii) 2 . P2 + 50 = P2 .
Answer:
Q7] Consider the six digits 1, 2, 3, 5, 6 and 7. Assuming that repetitions are not permitted.
Answer the following:
i) How many four digit numbers can be formed from the six digits 1, 2, 3, 5, 6 and 7?
ii) How many of these numbers are less than 4000?
iii) How many of the numbers in (i) are even?
iv) How many of the numbers in (i) are odd?
v) How many of the numbers in (i) are a multiple of 5?
vi) How many of the numbers in (i) contain both the digits 5 and 7?

Answer:
(i) The four digit number can be formed by filling up 4
blank spaces with the available 6 digits. Therefore
Number of four digit numbers = P(6, 4) = 360

(ii) If the four digit number is to be less than 4,000 then

the first digit must be 1, 2 or 3.
Therefore, the first space can be filled up in 3 ways. ↓
Corresponding to any one of these three ways, the 1,2,
remaining three spaces can be filled up with the 3
remaining five digits in P(5, 3) = 60 ways
Hence, Required number = 3 x 60= 180

(iii) If the four digit number is to be even, then the last

digit must be 2 or 6.
Therefore, the last space can be filled up in 2 ways.
↓
Corresponding to any one of these two ways, the
2,
remaining three spaces can be filled up with the
6
remaining five digits in P(5, 3) = 60 ways
Hence, Required number of even numbers = 2 x 60 =
120.
 (iv) If the four digit number is to be odd, then the last digit
must be 1 or 3 or 5 or 7
Therefore, the last space can be filled up in 4 ways.
↓
Corresponding to any one of these four ways, the
1,3,5,
remaining three spaces can be filled up with the
7
remaining five digits in P(5, 3) ways
Hence, Required number of even numbers =
4x60=240

(v) If the four digit number is to be a multiple of 5, then

the last digit must be 5
Therefore, the last space can be filled up in 1 way.
↓
the remaining three spaces can be filled up with the
5
remaining five digits in P(5, 3) ways
Hence, Required number of even numbers = 1x60 =
60

(vi) The digits 5 and 7 can occupy any two of the four
places in P(4, 2) = 12.
The remaining Two spaces can be filled up with the
remaining four digits in P(4, 2) = 12 ways
Hence, Required number of even numbers = 12 x 12
= 144 ways.

Q8] How many permutations of the letters A, B, C, D, E, F, G and H contain

(i) The string CDE?
(ii) THE STRINGS AB and FG?
(iii) The strings ABC and CDE?
(iv) The strings ABC and BED?

Answer:
(i) Considering CDE as one object, we have the following six objects: A, B, CDE, F, G,
H. These six objects can be permuted in P(6, 6) = 6 ! = 720 ways.
(ii) The objects AB, C, D, E, FG, H can be permuted in P(6, 6) = 720 ways.
(iii) The strings ABC and CDE contain the common letter C. If we include the strings
ABCDE in the permutations, it includes both the strings ABC and CDE. But, we
cannot use the letter C twice. Hence , we have the objects ABCDE, F, G and H.
These four objects can be permuted in 4 ! = 24 ways.
(iv) To include the two strings ABC and BED in the permutations, we require the letter
B twice, which is not allowed. Hence, the required number of permutations = 0.

Q9] (i)In how many ways can six men and four women sit in a row?
ii) In how many ways can they sit in a row if all the men sit together and all the women
sit together?
iii) In how many ways can they sit in a row if just the women sit together?
Iv) In how many ways can they sit in a row if just the men sit together?

Answer:
(i) Total number of persons = 6 + 4 = 10. Number of ways of arranging six men and
four women in a row = 10 ! = 36,28,800.
 (ii) Let us assume that all the men together can be considered as one unit and all the
women together can be considered as the second unit. These two units can be
arranged in 2 ! = 2 ways.
Corresponding to any one of these two ways, the men can be arranged among
themselves in 6 ! ways and the women can be arranged among themselves in 4 !
ways. Hence, the required number of ways = 2 ! x 6 ! x 4 ! = 34,560.
(iii) By considering all the women together as a single unit, we have seven objects.
These seven objects can be arranged in a row in 7 ! ways.
Corresponding to any one of these ways, the four women can be arranged among
themselves in 4 ! ways.
Hence, the required number of ways = 7 ! x 4 ! = 1,20,960.
iv) Number of ways in which women alone sit together
=(number of ways in which women sit together) – (number of ways in which
women sit
together and men sit together)
=1,20960 – 34,560
=86,400.

Q10] In how many ways can the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 be arranged so that
(i) 0 and 1 adjacent and in the order of 01.
(ii) 0 and 1 adjacent.
(iii) 0 and 1 are never adjacent.
Answer:
(i) Let us keep 0 and 1 together and consider as one unit in the order of 01.
Now, we have 9 digits which can be arranged in P(9, 9) = 9 ! = 3,62,880 ways.
Hence, the total number of ways in which 0 and 1 are in the order of 01 is 9! =
3,62,880.
(ii) Keeping 0 and 1 together and considering as one unit, we have 9 digits which can
be arranged in P(9, 9) = 9! = 3,62,880 ways.
But 0 and 1 can be arranged among themselves (i.e., 01, 10) in 2!=2 ways.
Hence, the total number of ways = 3,62,880 x 2 = 7,25,760.
(iii) The total number of ways the given ten digits can be arranged without any
restriction is P(10, 10) = 10!=36,28,800.
So, the total number of ways of arrangements in which 0 and 1 are never adjacent
=(Total number of ways without any restriction) – (Number of ways in which 0
and 1 are always adjacent)
= 36,28,800 – 7,25,760 = 29,03,040.

Q11] Suppose repetitions are not permitted, answer the following questions:
(i) How many three digit numbers can be formed from the six digits 2, 3, 5, 6, 7 and
9?
(ii) How many of these numbers are less than 400?
(iii) How many of these are even?
Answer:
(i) The three digit number can be formed by filling up 3
blank spaces with the available 6 digits.
Therefore, Number of four digit numbers = P(6, 3) = 6 6 5 4
x 5 x 4 = 120

(ii) If the three digit number is to be less than 400 then ↓

 the first digit must be 2 or 3.
Therefore, the first space can be filled up in 2 ways.
Corresponding to any one of these two ways, the
remaining two spaces can be filled up with the
remaining five digits in P(5, 2) ways 2,3
Hence, Required number =
5! 5 ! 2 . 120
2 . P ( 5 , 2 )=2. =2. =
(5−2 ) ! 3! 6
= 40.

(iii) If the three digit number is to be even, then the last

digit must be 2 or 6.
Therefore, the last space can be filled up in 2 ways.
Corresponding to any one of these two ways, the ↓
remaining two spaces can be filled up with the 2,
remaining five digits in P(5, 2) ways 6
Hence, Required number of even numbers =
5! 5 ! 2 . 120
2 . P ( 5 , 2 )=2. =2. = =40.
(5−2 ) ! 3! 6

Q12] In how many ways can four mathematics books, three history books, three chemistry
books and two sociology books be arranged on a shelf so that all books of the same subject
are together?
Answer:
(i) First, the books must be arranged on the shelf in four
units according to subject matter.

The first box can be filled by one of the four subjects,

4 3 2 1
the next by any three remaining subjects, the next by
any two remaining subjects and the last box can be
filled by the last subject.

Thus, there are 4 x 3 x 2 x 1 = 4! ways of arranging the books on the

shelf according to
subject matter.
Now, in each of the above cases, the mathematics books can be
arranged in 4! Ways,
the history books in 3! Ways, the chemistry books in 3! Ways and the
sociology
books in 2! Ways
Thus, there are 4! X 4! X 3! X 3! X 2! = 41,472 arrangements.

Combinations :- An unordered selection of ‘r’ elements from a set is called an ‘r –

combination’.
Thus, an r – combination is simply a subset with ‘r’ elements of the set.
The number of r – combinations of a set with ‘n’ distinct elements is denoted by

C(n, r) or n C r or ¿ ( n¿ ) ¿ ¿ n
Cr =
n!
0 ≤ r ≤n
¿ and defined as ( n−r )!.r ! , where and n is a non-negative
integer.
Q13] Find C ( n , 0 ) , C ( n , 1 ) ,C ( n , n ) ,C (n , n−1) .
Answer:
 n n! n! n!
C 0= = = =1 .
(i) ( n−0 )!. 0 ! n !. 1 n !
n n! n .(n−1) ! n
C1 = = = =n .
(ii) (n−1)!.1 ! (n−1 ) !. 1 1
n n! n! n! n!
C n= = = = =1.
(iii) ( n−n)!.n! 0 !.n ! 1.n ! n !
n n! n .(n−1 ) ! n n
C n−1 = = = = =n .
(iv) (n−(n−1 ))!.(n−1 )! (n−n+1) !.(n−1) ! 1 ! 1

Q14] Let ‘n’ and ‘r’ be non-negative integers with r≤n. Then show that C(n, r) = C(n, n-r).
Answer:
n!n
C r=
We know that, (n−r ) ! . r !
n n! n! n!
C n−r = = = =n C r .
RHS = (n−(n−r )) ! . (n−r) ! (n−n+r) !.(n−r) ! r ! . (n−r ) !
10
Ex. C 3= 10 C10−3 =10 C7 =120

Q15] A club has 25 members. How many ways are there to choose 4 members of the club
to serve on an executive committee?

Answer: The number of ways of selecting 4 members from 25 members

= Number of 4-combinations of a set with 25 elements.
25 25 ! 25 .24 .23 .22. 21 ! 25. 24 . 23 .22
C 4= = = =25 .23 .22=12 , 650 .
= (25−4 ) !. 4 ! 21 !.4 .3 . 2.1 4.3. 2. 1

Q16] How many bit strings of length 8 contain

(i) exactly five 1’s?
(ii) an equal number of 0’s and 1’s?
(iii) at least four 1’s?
(iv) at least three 1’s and at least three 0’s?
Answer:
(i) A bit string of length 8 can be considered to have eight positions,. These eight
positions can be filled up with exactly five 1’s and three 0’s. Therefore, the
required number of bit strings
8 8! 8! 8.7.6.5 ! 8.7.6.
C5 = = = = =56.
= (8−5) !.5 ! 3 ! . 5 ! 3.2.1.5 ! 3.2.1.
(ii) These eight positions can be filled up with four 1’s and four 0’s. Therefore, the
required number of bit strings
8 8! 8.7.6.5.4 ! 8.7.6.5
C 4= = = =70.
= (8−4) !.4 ! 4!. 4.3.2.1 4.3.2.1
(iii) These eight positions can be filled up with four 1’s and four 0’s; five 1’s and three
0’s; six 1’s and two 0’s; seven 1’s and one 0 or eight 1’s and no 0’s.
Therefore, the required number of bit strings
 = 8 C 4 + 8 C5 + 8 C6 + 8 C7 + 8 C 8
8! 8! 8! 8! 8!
¿ + + + +
4 !.4 ! 3 !.5 ! 2 !.6 ! 1 !.7 ! 0 !.8 !
8.7.6.5.4.3.2.1 8.7.6.5.4.3.2.1 8.7.6.5.4.3.2.1 8.7.6.5.4 .3.2.1 8.7.6.5.4.3.2.1
¿ + + + +
4 .3.2.1. 4.3.2.1 3.2.1.5.4.3.2.1 2.1.6.5.4 .3.2.1 1.7.6.5.4.3.2.1 1.8.7.6.5.4.3.2.1
¿70+56+28+8+1
¿163
(iv) These eight positions can be filled up with three 1’s an five 0’s; four 1’s and four
0’s; or five 1’s and three 0’s.
Therefore, the required number of bit strings
= 8 C 3 + 8 C 4 + 8 C5
8! 8! 8!
¿ + +
3 !.5 ! 4 !.4 ! 5 !.3 !
8.7.6.5.4.3.2.1 8.7.6.5.4.3.2.1 8.7.6.5.4.3.2.1
¿ + +
3.2.1.5.4.3.2.1 4.3.2.1.4.3.2.1 5.4 .3.2.1.3.2.1
¿56+70+56
¿182.

Q17] Suppose a department consists of 10 men and 15 women. How many ways are there
to form a committee with six members if it must have three men and three women?

Answer: Number of men in the department, n(M) = 10

Number of women in the department, n(W) = 15
We need six members to form a committee in which the number of men must be
equal to the number of women. Hence, the required number of ways
= 10 C3 ⋅ 15 C 3
10 ! 15 !
¿ ⋅
7 !.3 ! 3 ! .12 !
10.9.8.7! 15.14.13.12 ! 10.9.8 15.14.13
¿ ⋅ = ⋅
7 !.3.2.1 3.2.1.12! 3.2.1 3.2.1
¿120⋅455
¿54,600
Q18] Suppose a department consists of eight men and nine women. In how many ways can
we select a committee of
(i) three men and four women?
(ii) four persons that has at least one woman?
(iii) four persons that has at most one man?
(iv) four persons that has persons of both men and women?
(v) Four persons so that two specific members are not included?

Answer:
(i) The committee of three men and four women can be selected in
 = 8 C 3 ⋅ 9 C 4 ways
8! 9!
¿ ⋅
5 !.3 ! 5 !.4 !
8.7.6.5! 9.8.7.6.5 ! 8.7.6 9.8.7.6
¿ ⋅ = ⋅
5 !.3.2.1 5 !.4.3.2.1 3.2.1 4.3.2.1
¿56⋅126
¿7,056
(ii) The committee must have at least one woman. Therefore, we have the following
possibilities:
Three men and one woman; two men and two women; one man and three
women or four women. Hence, the required number of possibilities are
= 8 C 3 ⋅ 9 C 1 + 8 C 2 ⋅ 9 C 2 + 8 C 1 ⋅ 9 C3 + 8 C0 ⋅ 9 C 4
¿56⋅9+28⋅36+8⋅84+1⋅126
¿504+1008+672+126
¿2,310
(iii) The committee must have at most one man. Therefore, the possibilities are four
women and no men or three women and one man. Hence, the required number
of possibilities are
= 8 C 0 ⋅ 9 C 4 + 8 C1 ⋅ 9 C 3
¿1⋅126+8⋅84
¿126+672
¿798
(iv) The required committee must have persons of both men and women. The
possibilities are three men and one woman; two men and two women or one
man and three women. Therefore, the required number of possibilities is
= 8 C 3 ⋅ 9 C 1 + 8 C 2 ⋅ 9 C 2 + 8 C 1 ⋅ 9 C3
¿56⋅9+28⋅36+8⋅84
¿504+1008+672
¿2,184
(v) First, let us find the number of selections that contain the two specific members.
After removing the two specific members, the number of members remaining in
the department is 15 i.e., (9+8-2=15).
Thus, the remaining two members can be selected in C(15, 2) ways.
In each of these selections, if we include those two specific members removed, we
get C(15, 2) selections consisting of the two members.
Therefore, number of selections not including these two members
=C(17, 4) – C(15, 2)
=2,380 – 105
=2,275.

Q19] State and prove Pascal’s Identity.

Answer: Statement: Pascal’s identity can be stated as follows:
n+1
Let ‘n’ and ‘m’ be positive integers with n ≥ m. Then C m = n Cm−1 + n C m
Proof:
R . H . S . =n C m−1 + n C m
n! n!
= +
(n−(m−1 )) ! (m−1) ! (n−m)! m!
n! n!
= +
(n−m+1 ) ! (m−1 ) ! ( n−m)! m !
n! n!
= +
(n−m+1 ).(n−m) ! (m−1) ! (n−m)! m.(m−1 ) !
=
n!
[ 1
(n−m) ! (m−1 ) ! n−m+1 m
+
1
]
=
n!
[ m+n−m+1
(n−m) ! (m−1 ) ! (n−m+1). m ]
n ! .(n+1)
=
(n−m) !. (n−m+1 ) (m−1) !. m
(n+1) !
=
(n−m+1 ) ! m !
=n+1 C m
=L . H . S .

Permutations with Repetition :-

Def. 1 :- The number of r – permutations of a set of ‘n’ objects with repetition allowed is nr .

Def. 2 :- If there are n1 different objects of type-1, n2 different objects of type-2,

………………..,n k different objects of type-k, then the number of different permutations of ‘n’
n!
,
objects is
n1 ! .n2 ! .........n k ! n +n +.. ... .. ...+n k =n .
where 1 2

Q20] How many ways are there to assign three jobs to five employees if each employee can
be given more than one job?

Answer: There are three jobs and five employees.

We must assign three jobs to the five employees.
Also, we can give more than one job to each employee.
This implies that repetition is allowed.
Hence, the number of ways to assign three jobs to the five employees = 53=125.

Q 21]How many strings of six letters are there?

Answer: Since there are 26 letters and each letter can be used repeatedly, by the product
rule, the number of strings of six letters = 266 .

Q22] How many different strings can be made from the letters of the word “SUCCESS” using
all the letters?
Answer: The Word “SUCCESS” has totally 7 letters.
In this word “SUCCESS”, some of the letters are repeated.
The word “SUCCESS” contains three S’s, two C’s, one U and one E.
Using all the letters of the word “SUCCESS” the number of different strings
7! 7.6.5.4 .3.2.1
= = =420.
3 ! . 2 ! . 1 ! . 1 ! 3.2.1.2.1.1.1

Q23] How many different strings can be made from the letters of the word “ABRACADABRA”
using all the letters?

Answer: The Word “ABRACADABRA” has totally 11 letters.

In this word “ABRACADABRA”, some of the letters are repeated.
The word “ABRACADABRA” contains five A’s, two B’s, two R’s, one C and one D.
Using all the letters of the word “ABRACADABRA” the number of different strings
11 ! 11.10.9.8.7.6.5.4.3.2.1
= = =83160.
5 ! . 2 ! . 2 ! . 1 ! . 1 ! 5.4.3.2.1.2.1.2.1.1.1
Q24] How many different strings can be made from the letters of the word “LOGARITHM”
using all the letters?

Q25] How many different strings can be made from the letters of the word “EVERGREEN”
using all the letters?

Q26] How many different strings can be made from the letters of the word “ENGINEERING”
using all the letters?

Combinations with Repetitions :- If repetition of elements is allowed, then the number of

n+r−1
r – combinations from a set with ‘n’ elements is Cr .

Q27] How many ways are there to select three unordered elements from a set of five
elements when repetitions are allowed?

Answer: We have to select three unordered elements from a set of five elements.
When repetitions are allowed, the number of ways of selecting three unordered
n+r−1
elements from a set with five elements = C r =5+3−1 C 3 =7 C3 = 35.

Q28] How many ways are there to place 6 different balls into 9 different bins ?

Answer: The number of ways in which 6 different balls can be placed into 9 different bins
= (The number of 6 – combinations from a set of 9 elements when repetitions
are allowed
9+6−1 14
= C 6 = C 6 = 3003.
Q29] There are three boxes of identical red, blue and white balls, where each box contains
at least 10 balls. How many ways are there to select 10 balls if
(i) there is no restriction?
(ii) at least one white ball must be selected?
 (iii) at least one red ball, at least two blue balls and at least three white balls must be
selected?
(iv) Exactly one red ball must be selected?
(v) At most one white ball is selected?
(vi) Twice as many red balls as white balls must be selected?
Answer:
There are three kinds of balls and we have to select 10 balls.
(i) Since there is no restriction, repetitions are allowed.
n+r−1
C r =3+10−1 C 10 = 12 C 10=66.
Hence, the number of ways of selecting 10 balls =
(ii) We select one white ball and keep it separately. Then, we have to select nine balls
from the three kinds of balls and then include the first white ball in the selections.
3+9−1
C 9 = 11 C 9 =55
Hence, the required number of ways of selecting 10 balls =
(iii) We select one red ball, two blue balls and three white balls and keep them
separately. Then, we select four balls from three kinds of balls and include the first
six chosen balls in each selection.
3+4−1 6
Thus, the required number of ways of selecting 10 balls = C 4 = C 4 =15 .
(iv) We select one red ball and keep it separately. Then, we select nine balls from the
boxes containing blue and white balls and then include one red ball in each
selection.
2+9−1 10
Hence, the required number of ways of selecting 10 balls = C 9= C9 =10
(v) We select one red ball and one blue ball and keep them separately. Then, we
select eight balls from the two kinds of balls, namely blue and white, and include
the already chosen red and blue balls in each selection.
2+8−1 9
Thus, the required number of ways of selection = C 8= C 8 =9
(vi) We need at most one white ball. Hence, the selection must not contain a white ball
or contain one white ball.
Thus, the required number of ways of selection =
2+10−1
C 10+ 2+9−1 C 9 =11 C 10 + 10 C 9=11+10=21
(vii) The selection must contain 0 red and 0 white balls, 2 red and 1 white balls, 4 red
and 2 white balls or 6 red and 3 white balls.
Thus, the required number of ways of selection
=1+10−1 C 10 +1+7−1 C 7+ 1+ 4−1 C 4+ 1+1−1 C 1
¿ 10 C 10+7 C 7+ 4 C 4+1 C 1
¿1+1+1+1
¿4
Circular Permutations :- If objects of a given set are arranged in a line, we obtain a linear
permutation. On the other hand, if objects are arranged in a circle or any closed curve, we
get a circular permutation. Also, the number of circular permutations will be different from
the number of linear permutations.

The number of different circular arrangements of ‘n’ objects = (n – 1) !

Q30] Find the number of different circular arrangements of the five elements a , e ,i , o , u .
Answer: The number of different circular arrangements of the five elements = (5 – 1) !=4 !
=24.

Note:- If the number of clockwise circular permutations is equal to the number of anti-
clockwise circular permutations, then the number of different circular arrangements =
1
( n−1 ) ! .
2

Q31]If eight people P, Q, R, S, T, U, V, W are seated around a round table.

(i) How many different circular arrangements are possible, if arrangements are
considered the same when one can be obtained from the other by rotation?
(ii) If P, Q, R, S are males and T, U, V, W are females, in how many arrangements do
the sexes alternate?
Answer:
(i) Since the rotation does not alter the circular arrangements, the required number of
different circular arrangements = (8 – 1) ! = 7 ! = 5,040.
(ii) Let P, Q, R, S represent males and T, U, V, W represent females.
Since the rotation does not alter the circular arrangements, we can assume that P
occupies the top position, as shown below:

The remaining positions 1, 3, 5, 7 must be occupied by four females. This can be

done in P(4, 4) = 4 ! = 24 ways.
The places 2, 4, and 6 must be occupied by the remaining three males. This can
be done in P(3, 3) = 3 ! = 6 ways
Hence, the total number of required circular arrangements = 24 x 6 = 144.

Binomial Theorem

Binomial theorem is a fundamental concept in the study of Combinatorics. We can state

this theorem as follows:
Let ‘x’ and ‘y’ be any two variables and let ‘n’ be a non-negative integer. Then
( x + y )n =n C 0⋅x n⋅y 0 + n C 1⋅x n−1⋅y 1 + n C 2⋅x n−2⋅y 2 + n C3⋅x n−3⋅y 3 +¿⋅¿⋅¿⋅+ n C r⋅x n−r⋅y r +¿⋅¿⋅¿⋅+ n C n⋅x n−n⋅y n .
n
i. e . , ( x + y )n= ∑ n C r⋅x n−r⋅y r .
r=0

Note:
( x −y)n=n C0⋅xn⋅y0−n C1⋅xn−1⋅y1+n C2⋅xn−2⋅y2−n C3⋅xn−3⋅y3+¿⋅¿⋅¿⋅¿¿ +(−1)rn Cr⋅xn−r⋅yr+¿⋅¿⋅¿⋅+(−1)nn Cn⋅xn−n⋅yn.
n
i. e . , ( x − y )n =∑ (−1 )r n Cr⋅x n−r⋅y r .
r=0

Note: 1] the number of terms in the expansion of ( x + y )n is (n + 1).

2) In the expansion of ( x + y )n , n
C r⋅x n−r⋅y r is called the general term or T th term in the
r+1
n n
expansion of ( x + y ) , Tr+1 = C r⋅x n−r⋅y r .
3] The sum of the powers of the variables in each and every terms in the expansion of
( x + y )n is n.

4] In the expansion ( x + y )n , n C 0 , n C 1 , n C 2 , n C 3 , ......., n C n are called the binomial coefficients.

Q32. Find the expansion of (x + y)6.

Answer:
( x + y )6 =6 C 0⋅x 6⋅y 0 + 6 C1⋅x 6−1⋅y 1 + 6 C 2⋅x 6−2⋅y 2 + 6 C 3⋅x 6−3⋅y 3 + 6 C 4⋅x 6−4⋅y 4 + 6 C5⋅x 6−5⋅y 5 + 6 C 6⋅x 6−6⋅y 6 .
( x + y )6 =1⋅x 6⋅1+6⋅x5⋅y 1 +15⋅x 4⋅y 2 +20⋅x 3⋅y 3 +15⋅x 2⋅y 4 + 6⋅x 1⋅y 5 +1⋅1⋅y 6 .
( x + y )6 =x 6 +6⋅x 5⋅y +15⋅x 4⋅y 2 + 20⋅x 3⋅y 3 +15⋅x 2⋅y 4 +6⋅x⋅y 5 + y 6 .

Q33. Find the expansion of (x - y)5.

Answer:
( x − y )5=5 C 0⋅x 5⋅y 0 −5 C1⋅x 5−1⋅y 1 + 5 C 2⋅x5−2⋅y 2−5 C 3⋅x 5−3⋅y 3 + 5 C 4⋅x 5−4⋅y 4 −5 C 5⋅x 5−5⋅y 5 .
( x − y )5=1⋅x5⋅1−5⋅x 4⋅y 1 +10⋅x 3⋅y 2 −10⋅x 2⋅y 3 +5⋅x 1⋅y 4 −1⋅1⋅y 5 .
( x − y )5=x 5 −5⋅x 4⋅y+10⋅x 3⋅y 2 −10⋅x 2⋅y 3 +5⋅x⋅y 4 − y 5 .

Q34. Find the expansion of (2x + 3y)4.

Answer:
( 2 x +3 y )4 =4 C 0⋅(2 x )4⋅(3 y )0 + 4 C1⋅(2 x )4−1⋅(3 y )1 + 4 C 2⋅(2 x )4−2⋅(3 y )2 + 4 C3⋅(2 x ) 4−3⋅(3 y )3 + 4 C 4⋅(2 x ) 4−4⋅(3 y )4 .
( 2 x +3 y )4 =1⋅16⋅x 4⋅1+4⋅8⋅x 3⋅3⋅y 1 +6⋅4⋅x 2⋅9⋅y 2 +4⋅2⋅x 1⋅27⋅y 3 +1⋅1⋅81⋅y 4 .
( 2 x +3 y )4 =16⋅x 4 +96⋅x 3⋅y+216⋅x 2⋅y 2 +216⋅x⋅y 3 +81⋅y 4 .

Q35. Find the expansion of (3x – 2y )5.

( 3 x − 2 y )5 =5 C0⋅(3 x )5⋅(2 y ) 0−5 C 1⋅(3 x )5−1⋅(2 y )1 + 5 C 2⋅(3 x )5−2⋅(2 y )2−5 C 3⋅(3 x )5−3⋅(2 y )3
Answer: + 5 C 4⋅(3 x )5−4⋅(2 y ) 4 −5 C 5⋅(3 x )5−5⋅(2 y )5 .
( 3 x − 2 y )5 =1⋅243⋅x5⋅1−5⋅81⋅x 4⋅2⋅y 1 +10⋅27⋅x3⋅4⋅y 2 −10⋅9⋅x 2⋅8⋅y 3
+5⋅3⋅x 1⋅16⋅y 4 −1⋅1⋅32⋅y 5 .
( 3 x − 2 y )5 =243⋅x 5 −810⋅x 4⋅y+1080⋅x 3⋅y 2−720⋅x 2⋅y 3 +240⋅x 1⋅y 4 −32⋅y 5 .

Q36. Find the 4th term in the expansion of (3x + 2y)6.

6
Answer: The 4th term in the expansion of (3x + 2y)6 is T4 = T3+1 = C 3⋅(3 x )6−3⋅(2 y )3 .

T4 = 20⋅27⋅x 3⋅8⋅y 3 =4320⋅x 3⋅y 3 .

Q37. Find the 5th term in the expansion of (2x – 2y)6.

Answer: The 5th term in the expansion of (2x - 2y )6 is T5 = T4+1 =

(−1 )5 6 C 4⋅(2 x )6−4⋅(3 y )4 .

T5 = −15⋅4⋅x2⋅81⋅y 4 =−4860⋅x 2⋅y 4 .

Q38. Find the coefficient of x5.y8 in (x + y)13 .

Answer: From the binomial theorem, we have
13
( x + y )13 =∑ 13 C r⋅x 13−r⋅y r ⇒ T r+1= . 13 Cr⋅x 13−r⋅y r
r=0
Substitution r = 8, we get the coefficient of x 5.y8 in the expansion as
T th term in ( x + y )13=13 C 8⋅x13−8⋅y 8 =1287⋅x 15⋅y 8 .
8+1
Therefore, the coefficient of x5.y8 in (x + y)13 is 1287.

Q39. Find the coefficient of x101.y99 in (2x - 3y)200 .

Answer: From the binomial theorem, we have
200
( 2 x −3 y )200 =∑ (−1 )r 200 C r⋅(2 x )200−r⋅(3 y )r ⇒ T r+1 =. (−1 )r 200 C r⋅(2 x )200−r⋅(3 y )r
r=0
Substitution r = 99, we get the coefficient of x 101.y99 in (2x - 3y)200 .
200
T th term in ( 2 x −3 y ) =(−1 )99⋅200 C 99⋅( 2 x )200−99⋅( 3 y )99 =−200 C 99⋅2101⋅x 101⋅399⋅y 99
99+1
200
Therefore, the coefficient of x101.y99 in (2x - 3y)200 is − C 99⋅2101⋅3 99 .

Q40. Find the independent of x in the expansion of

( 3 x+
1 8
2x )
.

Answer: Let
T
r+1th term be the independent of x in the expansion of
( 3 x+
1 8
2x )
.

Therefore,
1 r 8
( ) ( )( ) () ()
r
8 8−r 8−r 8−r 1 1 r 8 8−r 1
r
8−r−r 8 8−r 1
r
T r+1=. C r⋅(3 x ) ⋅ = C r⋅3 ⋅x ⋅ ⋅ = C r⋅3 ⋅ ⋅x = C r⋅3 ⋅ ⋅x 8−2 r
2x 2 x 2 2

(3 x + 21x )
8

The term independent of ‘x’ in the expansion of only when 8 – 2r = 0 i.e., r = 4.

( )
8
1
3 x+
Therefore, the term independent of ‘x’ in the expansion of 2x is

T 4+1 =.=8 C 4⋅38−4⋅ ()

1 4 8−2( 4 )
2
⋅x
1 2835
=70⋅81. =
16 8
.
n
∑ n C r =2n .
Q41. If ‘n’ is a non-negative integer, then show that r=0

Answer: By Binomial theorem, we have 2n=(1+1)n

n
= ∑ nCr .1
n−r
. 1r
r=0
n
= ∑ nCr
r=0
n
∑ n C r =2n .
Therefore, r=0
n
∑ (−1 )r⋅n Cr =0.
Q42. If ‘n’ is a positive integer, show that r=0
 n n
0=0 =[ 1+ (−1 ) ] =∑ C r⋅1
n
n n n−r
⋅(−1 ) = ∑ n C r⋅(−1 )r
r

Answer: By binomial theorem, we have r=0 r=0

n
∑ (−1 )r⋅n Cr =0.
Therefore, r=0
n
∑ 2r⋅n C r =3 n .
Q43. If ‘n’ is a non-negative integer, show that r=0
n n
3n =( 1+ 2)n =∑ n C r⋅1n−r⋅( 2 )r = ∑ n C r⋅2 r .
Answer: By binomial theorem, we have r=0 r=0
n
∑ 2r⋅n C r =3 n .
r=0

Therefore,

MULTINOMIAL COEFFICIENTS

Multinomial Coefficient: Given non-negative integers k 1 , k 2 , k 3 , … … .., k m and

n = k 1+ k 2+ k 3 +… … ..+k m the multinomial coefficient ( k , k , kn , .., k )

1 2 3 m
is defined by

( n
)
k 1 , k 2 , k 3 , .., k m
=
n!
k 1 ! k 2 ! , … ….. , k m !
. In fact, binomial coefficients are special instances of

multinomial coefficients. Since. For 0 ≤ k ≤ n , we have ( nk)= k ! ( n−k

n!
) ! k ,n−k )
=(
n
.

Q44. Compute (3 ,102 ,5) .

Answer: (3 ,102 ,5)= 3 !102 !!5 ! =2520.
Q45. Compute ( 4 ,100 , 6).
Answer: ( 4 ,100 , 6).= 4 !100 !!6 ! =210.
The Multinomial Theorem:
Let a 1 , a2 , … … , am ∈ R∧n ∈ Z withn ≥ 1. Then

∑
k1 k k
¿
0≤k1 , k 2 , .. . . .. , k m≤n a1 ¿¿ a . aa22 . . .. . aamm .¿
k +k +. ... ..,+k =n ¿
1 2 m

Here, the sum is indexed over all ordered m-tuples of integers

k 1 ,k 2 ,......,k m such that
0≤k 1 , k 2 ,. . .. .. , k m ≤n and k 1 +k 2 +.. . .. .+k m=n.
Note: The number of terms in the expansion of (
a1 + a2 +. .. .. . ..+ am )n
is (n+ m−1
n )
.

Q46. Find the number of terms in the expansion of ( u+ v +2 w+ x +3 y + z )11 .

Answer: Here n = 11; m = 6.

Then the number of terms in the given expansion = (11+116−1)=(1611)=4368.

Q47. Use the Multinomial Theorem to expand ( x + y + z )4 .
Answer: Here, the sum in our expansion is indexed over the triples ( k 1 , k 2 , k 3 ) such that 0 ≤ k 1 , k 2 , k 3 ≤ 4 and
k 1+ k 2 ,+ k 3=4 That is, the triples
(4, 0, 0) (0, 4, 0) (0, 0 , 4) (3, 1, 0) (3, 0, 1) (0, 3, 1) (1, 3, 0)
(1, 0, 3) (0, 1, 3) (2, 2, 0) (2, 0, 2) (0, 2, 2) (2, 1, 1) (1, 2, 1)
(1, 1, 2) index our sum.

In each case, the triple (k 1 , k 2 , k 3 ) corresponds to the term ( k , k4 , k ) x

1 2 3
k1
y k z k . That is, the triple determines
2 3

both the exponents on x, y, and z and the bottom row of the multinomial coefficient. For example, the triple (3, 0,

1) corresponds to the term (3 , 40 , 1) x y z =4 x z.

3 0 1 3
Thus, in total, we get

∑
k k k
¿ 0≤k1 , k2 , k 3≤4 ¿¿ x 1 y 2 z 3 ¿
k +k +k =4 ¿
1 2 3

=x +4 x 3 y +4 x 3 z+6 x 2 y 2 +12 x 2 yz+6 x 2 z 2 +4 xy 3 +4 xy 2 z+12 xyz 2 +4 xz 3 + y 4 +4 y 3 z+6 y 2 z 2 +4 yz 3 +z 4

4

2
Q48. Use the Multinomial theorem to expand ( w +2 x +3 y 4 z ) .
Ans: Here the sum in our expansion is indexed over the ordered 4-tuples (k 1, k2, k3, k4) such
that 0 ≤ k1, k2, k3, k4 ≤ 2 and k1+k2 + k3 + k4 = 2. That is, the ordered 4-tuples.
(2, 0, 0, 0) (1, 1, 0, 0) (1, 0, 1, 0) (1, 0, 0, 1) (0, 2, 0, 0)
(0, 1, 1, 0) (0, 1, 0, 1) (0, 0, 2, 0) (0, 0, 1, 1) (0, 0, 0, 2)
Index our sum. Thus, we get

∑
k1 k2 k3 k4
¿ 0≤k1 , k 2 , k3 , k4 ≤2 ¿ ¿ w (2 x ) (3 y ) (4 z) ¿
k +k +k +k =2 ¿
1 2 3 4
=w +4wx+6wy+8wz+4x2+12xy+16xz+9y2+24yz+16z2 .
2

Q49. (Extracting a Coefficient). What is the coefficient of u2w3x4y2 in the expansion of (u+v+2w+x+3y+z)11 ?
Ans: The expansion includes the summand

( 11
2,0,3,4,2,0 )
⋅u 2 v 0 (2w )3 x 4 (3 y)2 z 0 =6930 u2 8w 3 x 4 9 y 2 =4989600 u 2 w3 x 4 y 2
Hence, the desired coefficient is 49,89,600.

** ** **
UNIT – III :: PART - 2 :: RECURRENCE RELATIONS
Recurrence Relation : An equation that expresses a n in terms of one or more of the
previous terms of the sequence, namely a 0 , a 1 , a2 , … … . , an−1 for all integers ‘n’ with
n ≥ n0 w h ere n 0 is a non-negative integer is called a recurrence relation for the sequence {an }
or a difference equation.

If the terms of a sequence satisfy the recurrence relation, then the sequence is called
a solution of the recurrence relation.

Q1] Let {an } be a sequence that satisfies the recurrence relation a n=a n−1 +3. a n−2 for n ≥2 and
a 0=1∧a1=2. Find the values of a 2∧a3 .

Q2] Find the first five terms of the sequence defined by the recurrence relation
a n=n . an−1 +n . an−2 for all n ≥2 a 0=1∧a1=1.
2

Q3] Determine whether the sequence {an } , where a n=−n+2 is a solution of the recurrence
relation a n=a n−1 +2. a n−2+2 n−9 for all n ≥ 2 .

Q4] By using an iterative approach, find the solution of recurrence relation

a n=a n−1 +2 , ∀ n ≥1 , a0 =3.

Fibonacci Sequence :- The sequence {0, 1, 1, 2, 3, 5, 8, 13, …….} is called Fibonacci Sequence.
Its recurrence relation is F n=F n−1−Fn−2 , ∀ n≥ 2 , w h ere F 0=0∧F1=1. The conditions
F 0=0∧F1=1 are called initial conditions.

Solution of Linear Homogeneous Recurrence Relations with constant Coefficients :-

A Recurrence Relation of the form a n=c 1 an−1 +c 2 an−2+ … … … … ..+c k an−k where c 1 , c2 , … . c k are
real numbers and c k ≠ 0, is called Linear Homogeneous Recurrence Relation of degree ‘k’ with
constant coefficients.

Note:- Degree is the difference between the greatest and lowest subscripts of the members
of the sequence occurring in the Recurrence Relation.

Note:- If F(n) = 0, then the recurrence relation is said to be homogeneous, otherwise, it is

said to be non-homogeneous recurrence relation.

Characteristic roots :- Consider the recurrence relation a n=c 1 an−1 +c 2 an−2+ … … … … ..+c k an−k
where c 1 , c2 , … . c k are real numbers and c k ≠ 0.

The Characteristic equation of the recurrence relation given above is

k k−1 k −2 1
r −c 1 r −c 2 r −… … … . c k−1 r −c k =0.

The solutions of the characteristic equation are called the characteristic roots.

Characteristic equation, roots and solutions for 2 nd degree homogeneous

recurrence relations :-

Consider the recurrence relation of the form a n=c 1 an−1 +c 2 an−2 , ∀ n ≥ 2.

The characteristic equation is r 2−c1 r−c 2=0.

Let the roots of the characteristic equation be r 1 , r 2.

Case (i) : If r 1 , r 2. are real and distinct, then the solution is a n=α 1 . r n1 +α 2 . r n2 , w h ere α 1∧α 2 are
arbitrary constants.

Case (ii) : If r 1 , r 2. are real and equal, then the solution is a n=(α ¿ ¿ 1+ α 2 .n) r n , w h ere α 1∧α 2 ¿ are
arbitrary constants.

Case (iii) : If r 1 , r 2. are complex numbers, say a ± bi , then the solution is

r =√ [ a +b ]
n 2 2
a n=r .(α 1 . cos nθ+α 2 . sin nθ), w h ere α 1∧α 2 are arbitrary constants and and

θ=tan−1 ( ba ) .
Q5] Solve the Recurrence relation a n=5. an−1−6. a n−2 , for n ≥2 , w h ere a0=1 , a1=0.

Q6] Solve the Recurrence relation a n=2. an−1 +a n−2−2. an−3 , for n ≥ 3 ,

w h ere a0=3 , a1=6 a2=0.

Q7] Solve the Recurrence relation a n=9. an −1−16.a n−2 , for n ≥2 , w h ere a0=16 , a1=80.

Q8] Solve the Recurrence relation a n=2. an−1−2. a n−2 , for n ≥2 , w h ere a0=1 , a1=2.

Q9] Find an explicit formula for the Fibonacci numbers.

Solution of Non-Homogeneous Recurrence Relation :- A linear non-homogeneous

recurrence relation with constant coefficients of degree ‘k’ is a recurrence relation of the
form a n=c 1 an−1 +c 2 an−2+ … … … … ..+c k an−k +G ( n ) , where c 1 , c2 , … . c k are real numbers and c k ≠ 0,
and G(n) is a function not identically zero depending only on ‘n’.

Procedure for solving non-homogeneous finite order Linear Recurrence Relation :-

To solve the recurrence relation a n−c 1 an−1−c 2 an−2−… … … … ..−c k an−k =G ( n ) , we have to adopt
the following procedure.
(H )
Step – I : We obtain the homogeneous solution a n .

First, we write the associated homogeneous recurrence relation

i.e., a n−c 1 an−1−c 2 an−2−… … … … ..−c k an−k =0

(H )
then, we find its general solution, which is called the homogeneous solution a n .

Step – 2: We obtain the particular solution a(P

n
)
.

There is no general procedure for finding the particular solution of a recurrence relation.
However, if G(n) has any one of the following forms.

(i) Polynomial in ‘n’

(ii) A constant, C
 (iii) Powers of constant.

Then we may guess the forms of the particular solution and exactly find out by the method
of undermined coefficients.

Particular Solution for given G(n):

S.NO. G(n) Form of Particular Solution

1. A Constant, C A Constant, ‘d’
2. A Linear function c 0 +c 1 .n A Linear function d 0 +d 1 . n
n d 0 +d 1 . n
2
n d 0 +d 1 . n+d 2 .n
2

An m t h degree polynomial
2 k
c 0 +c 1 .n+ c . n +… … ..+ cm . n 2
d 0 +d 1 . n+d 2 .n + … … ..+ d m .n
k

3. Power of constant, say r n , r ∈ R dr

n

Step – 3 : We substitute the guess from Step – 2 into the recurrence relation. If the guess is
correct, then we can determine the unknown coefficient of the guess. If we are not able to
determine the coefficients, then our guess is wrong and hence we go to step – 2.

Step – 4 : The general solution of the recurrence relation is the sum of the homogeneous
and particular solutions i.e., a n=a(H ) (P)
n + an .

Step – 5 : If no initial conditions are given, then step – 4 will give the solution. If ‘n’ initial
conditions are given, then we get ‘n’ equations with ‘n’ unknowns. Solving the system, we
get a complete solution.

Q10] Solve the recurrence relation a n−a n−1 −6. an−2=−30 , ∀ n ≥2 , wit h a0=20 ,∧a 1=−5.

Q11] Solve the recurrence relation a n−2. an−1 +a n−2=2 , ∀ n ≥ 2 , wit h a 0=25 ,∧a1=16.

Q12] Solve the recurrence relation a n−7. an−1 +10. an−2=6+ 8 n , ∀ n ≥ 2 , wit h a 0=1 ,∧a1=2.

Q13] Solve the recurrence relation a n−4. a n−1+ 4. an−2=n 2 , ∀ n ≥2 , wit h a0=2,∧a1=10.

Q14] Solve the recurrence relation a n−2. an−1−3. a n−2=5n , ∀ n ≥ 2 , wit h a 0=−2 ,∧a1=1.

Q15] Solve the RR a n−2 . an−1−2. an−2=5 n , ∀ n ≥ 2, wit h a0 =1 , a1=1.

Q16] Solve the recurrence relation a n−3. an−1−4. an−2=4n .

Q17] Solve the recurrence relation a n−4. a n−1+ 4. an−2=3 n+2 n , ∀ n ≥2 , wit h a0=1 ,∧a1=1.

Q18] Solve the recurrence relation a n=4. a n−1−4. a n−2 +(n+1)2n .

Q19] Solve the R.R. a n+ 2n . a n−1−3 n(n−1). an−2=0 , ∀ n ≥ 2 , wit h a 0=1 ,∧a 1=2.

Q20] Solve the R.R. a 2n−2. a2n−1=0 , ∀ n ≥ 1, wit h a0 =2.

Q21] Solve the RR a 2n+2−5. a 2n+1 +4. a2n=0 , ∀ n≥ 0 wit h a0 =0 , a1=13.

Q22] Solve the R.R. √ an −√ an−1−2. √ an−2=0 , ∀ n ≥ 2 , wit h a0 =1 , a1=1.
Q23] Solve the R.R. a n+2−5. a n+1 +6. an=2 , ∀ n ≥ 0 , wit h a 0=1 ,∧a 1=−1.

Q24] solve the RR a n+2−4 . an +1+ 4. an =2n .

Q25] Solve the RR S ( n+2 ) −S ( n+1 )−2. S ( n )=n 2 .

Q26] Solve the RR T ( n )=4. T ( n−1 ) +2n, ∀ n ≥1 , wit h T ( 0 ) =6.

Generating Functions : The generating function of a sequence a 0 , a 1 , a2 , … … . of real

numbers is written as the series given below :
∞
G ( z )=a 0+ a1 . z +a 2 . z + … …..+ an . z +… … …=∑ an . z n .
2 n

n=0

Q27] Find the generating function for the sequence 2, 2, 2, 2, 2, 2.

Q28] Find the generating function for the sequence 1, 2, 3, 4, ……… .

Note: The generating function of a sequence a 0 , a 1 , a2 , … … . is also denoted by <

a 0 , a 1 , a2 , … … . >.

Q29] Find the generating function for the sequence < 5, 3, -4, -2, 0, 1 > .

Q30] Find the closed form expression of the generating function for the sequence
2 3
1 , a , a , a , …. . .

Solution of Recurrence Relation using Generating Functions :

Q31] Use generating functions to solve the RR a n=3. an−1 +2 , ∀ n ≥ 1 , wit h a 0=1

Q32] Use generating functions to solve the RR a n−2. an−1−3. a n−2=0 , ∀ n≥ 2 , wit h a0=3 , a1 =1.

Q33] Use generating functions to solve the RR a n−8 . an−1 +2. an−2−18 an−3=0 , ∀ n ≥3.

Q34] Use generating functions to solve the RR a n=4 . an−1−4.a n−2+ 4 n , ∀ n ≥ 2, wit h a0 =2 ,a 1=8.

Q35] Use generating functions to solve the RR a n=a n−1 +2. ( n−1 ) , ∀ n ≥ 1, wit h a0 =3.

Q36] Use generating functions, solve the RR a n+2−5 . a n+1 +6. an=2 , ∀ n ≥0 , wit h a0 =1 , a1=−1.

Q37] Use generating functions, solve the RR a n+2−2 . an +1+ an=2n , ∀ n ≥ 0 , wit h a 0=2 , a1=1.

** ** **