BCS405A

Discrete Mathematical Structures

(For the 4th Semester Computer Science and Engineering Stream)

Module 2
Properties of Integers & Principles of Counting
 Content

[Link] Topic Page No

1 Syllabus 1-1
2 Mathematical Induction-well Ordered Principle 1-1
3 Problems on Mathematical Induction 1-8
4 Recursive Definition 9-12
5 The Rules of Sum and Product 13-14
6 Permutations 15-17
7 Combinations 18-21
8 Binomial and Multinomial Theorems 22-24
9 Combination with Reputations 25-27
 MODULE 2

PROPERTIES OF INTEGERS & PRINCIPLES OF COUNTING

☻Syllabus:

Properties of the Integers: The Well Ordering Principle – Mathematical Induction.

Fundamental Principles of Counting: The Rules of Sum and Product, Permutations, Combinations – The
Binomial Theorem, Combinations with Repetition.

☻Mathematical Induction:

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a

statement 𝑃(𝑛) holds for every natural number 𝑛 = 0, 1, 2, 3, … …. i.e., the overall statement is a sequence of
infinitely many cases 𝑃(0), 𝑃(1), 𝑃(3), … … … ..

Well ordering principle:

Every non empty subset of 𝑍 +contains a smallest element. (we often express this by saying that 𝑍+ is well
ordered).

Finite induction principle (principle of Mathematical induction):

Let 𝑆(𝑛) denote an open mathematical statement that involves one or more occurrences of the variable n.
Which represents a positive integer

(a) If 𝑆(1) is true; and

(b) If whenever 𝑆(𝑘)is true (for some particular but arbitrarily chosen 𝑘 ∈ 𝑍+), then 𝑆 (𝑘 + 1)is true,
then 𝑆(𝑛) is true for all 𝑛 ∈ 𝑍+.

Proof:

Let 𝑆(𝑛) be such an open statement satisfying conditions (a) and (b) and let 𝐹 = {𝑡 ∈ 𝑍 +/ 𝑆(𝑡) is false}. We
wish to prove that 𝐹 = ∅ so to obtain a contradiction we assume that 𝐹 ≠ ∅. Then by the well-ordering
Principle, F has a least element. Since 𝑆(1) is true. It follows that 𝑆 ≠ 1. so 𝑠 > 10, and consequently 𝑠 −
1 ∈ 𝑍+. With 𝑠 − 1 ∉ 𝐹, 𝑆(𝑠 − 1) we have true. So, by condition (b) it follows that 𝑆((𝑠 − 1) + 1) = 𝑆(𝑠)
is true, contradicting 𝑠 ∈ 𝐹. This contradiction arose from the assumption that 𝐹 ≠ ∅. Consequently 𝐹 = ∅.

Problems:

1. Prove by mathematical induction that, for all positive integers 𝑛 ≥ 1.

1
1 + 2 + 3 + ⋯ ⋯ ⋯ + 𝑛 = 𝑛(𝑛 + 1)
2

Solution:

Here, we have to prove the statement

1
𝑆(𝑛) = 1 + 2 + 3 + ⋯ ⋯ ⋯ + 𝑛 = 𝑛(𝑛 + 1) for all integers 𝑛 ≥ 1.
2
Basic step: We note that 𝑆(1) is the statement
1
1 = ∙ 1 ∙ (1 + 1)
2

Which is clearly true. thus, the statement 𝑆(𝑛)is verified for 𝑛 = 1.

Induction step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we

assume that the following statement is true:

1
𝑆(𝑘) = 1 + 2 + 3 + ⋯ ⋯ ⋯ + 𝑘 = ∙ 𝑘(𝑘 + 1)
2

Using this we find that (by adding (𝑘 + 1) to both side)

1
𝑆(𝑘) = 1 + 2 + 3 + ⋯ ⋯ ⋯ + 𝑘 + (𝑘 + 1) = ∙ 𝑘(𝑘 + 1) + (𝑘 + 1)
2
1
= (𝑘 + 1) { 𝑘 + 1}
2
1
= (𝑘 + 1)(𝑘 + 2)
2

This is precisely the statement 𝑆(𝑘 + 1). Thus, on the basis of the assumption that 𝑆(𝑛) is true for 𝑛 = 𝑘 ≥
1, the truth ness of 𝑆(𝑛) for 𝑛 = 𝑘 + 1 is established.
𝑛(𝑛+1)(2𝑛+1)
2. Prove that, for each 𝑛 ∈ 𝑍+ ∑𝑛𝑖=1 𝑖2 =
6

OR
𝑛(𝑛+1)(2𝑛+1)
Prove that, for each 𝑛 ∈ 𝑍+, 12 + 22 + 32 + ⋯ ⋯ ⋯ + 𝑛2 =
6

Solution:

Let S(n) denote the given statement.

Basic step: We note that is 𝑆(1) is the statement

1
12 = ∙ 1 ∙ (1 + 1) ∙ (2 + 1) which is clearly true.
6

Induction Step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we
assume that the following statement is true.
𝑘(𝑘+1)(2𝑘+1)
𝑆(𝑘) = 12 + 22 + 32 + ⋯ ⋯ ⋯ + 𝑘2 = .
6

Adding (𝑘 + 1) 2 to both sides of this, we obtain

𝑘(𝑘+1)(2𝑘+1)
𝑆(𝑘) = 12 + 22 + 32 + ⋯ ⋯ ⋯ + 𝑘2 + (𝑘 + 1)2 = + (𝑘 + 1)2
6

𝑘 (2𝑘+1)
= (𝑘 + 1) { + (𝑘 + 1)}
6
 1
= (𝑘 + 1){𝑘(2𝑘 + 1) + 6(𝑘 + 1)}
6
1
= (𝑘 + 1){2𝑘2 + 𝑘 + 6𝑘 + 6}
6
1
= (𝑘 + 1){2𝑘2 + 7𝑘 + 6}
6
1
= (𝑘 + 1)(𝑘 + 2)(2𝑘 + 3)
6

This is precisely the statement 𝑆(𝑘 + 1). Thus, on the basis of the assumption that 𝑆(𝑛) is true for 𝑛 = 𝑘 ≥
1, the truth ness of 𝑆(𝑛) for 𝑛 = 𝑘 + 1 is established.

3. By mathematical induction, Prove That (𝑛!) ≥ 2𝑛−1 for all integers𝑛 ≥ 1.

Solution:

Basic step: For 𝑛 = 1, 𝑆(𝑛) reads (1!) ≥ 21−1 which is obviously true. Thus 𝑆(𝑛) is verified for 𝑛 = 1.

Induction step: We assume that 𝑆(𝑛) is true for 𝑛 = 𝑘, where 𝑘 is an integer ≥ 1; that is, we assume that

(𝑘!) ≥ 2𝑘−1 , or 2𝑘−1 ≤ 𝑘! is true

2𝑘 = 2 ∙ 2𝑘−1 ≤ 2 ∙ 𝑘!

≤ (𝑘 + 1) ∙ 𝑘!, because 2 < (𝑘 + 1) for 𝑘 ≥ 1

= (𝑘 + 1)!

(𝑘 + 1)! ≥ 2𝑘

This is precisely the statement 𝑆(𝑛) for 𝑛 = 𝑘 + 1. Thus, on the assumption that 𝑆(𝑛)is true for 𝑛 = 𝑘 ≥ 1,
We have proved that 𝑆(𝑛) is true for 𝑛 = 𝑘 + 1.

Hence, by mathematical induction, it follows that the statement 𝑆(𝑛) is true for all integers 𝑛 ≥ 1.

4. Prove that every positive integer 𝑛 ≥ 24 can be written as a sum of 5’s and/or 7’s.

Solution:

Basic step: We note that 24 = (7 + 7) + (5 + 5)

This shows 𝑆(24) is true.

Induction step: We assume that 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 ≥ 24. Then

𝑘 = (7 + 7 + ⋯ ⋯ ) + (5 + 5 + ⋯ ⋯ )

Suppose this representation of 𝑘 has 𝑟 number of 7’s and 𝑠 number of 5’s. Since 𝑘 ≥ 24 we should have
𝑟 ≥ 2 and 𝑠 ≥ 2.

Using this representation of 𝑘, we find that

 +_⋯ ⋯¸) + (⏟5 + 5_
𝑘 + 1 = {(⏟7 + 7_ +_⋯ ⋯¸)} + 1
𝑟 𝑠

= {⏟ ¸) + (7 + 7) + (⏟5_+ 5_
(7_+ 7_+ ⋯_⋯ +_⋯ ⋯¸)} + 1
𝑟−2 𝑠

= {⏟
(7 + 7_ ( 5 + 5_
+_⋯ ⋯¸) + ⏟ +_⋯ ⋯¸)}
𝑟−2 𝑠+3

This shows that 𝑘 + 1is sum of 7’s and 5’s. Thus, 𝑆(𝑘 + 1) is true.

5. Prove by mathematical induction that, for all positive integers 𝑛 ≥ 1.

1
1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ⋯ ⋯ ⋯ + 𝑛(𝑛 + 1) = 𝑛(𝑛 + 1)(𝑛 + 2)
3

Solution:

Here, we have to prove the statement

1
𝑆(𝑛) = 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ⋯ ⋯ ⋯ + 𝑛(𝑛 + 1) = 𝑛(𝑛 + 1)(𝑛 + 2) for all integers 𝑛 ≥ 1.
3

Basic step: We note that 𝑆(1) is the statement

1
1 ∙ 2 = ∙ 1 ∙ (1 + 1) ∙ (2 + 1)
3

Which is clearly true. thus, the statement 𝑆(𝑛)is verified for 𝑛 = 1.

Induction step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we

assume that the following statement is true:

1
𝑆(𝑘) = 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ⋯ ⋯ ⋯ + 𝑘(𝑘 + 1) = 𝑘(𝑘 + 1)(𝑘 + 2)
3

Using this we find that (by adding (𝑘 + 1)(𝑘 + 2) to both side)

𝑆(𝑘) = 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ⋯ ⋯ ⋯ + 𝑘(𝑘 + 1) + (𝑘 + 1)(𝑘 + 2)

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

1
= (𝑘 + 1)(𝑘 + 2) { 𝑘 + 1}
3
1
= (𝑘 + 1)(𝑘 + 2)(𝑘 + 3)
3

This is precisely the statement 𝑆(𝑘 + 1). Thus, on the basis of the assumption that 𝑆(𝑛) is true for 𝑛 = 𝑘 ≥
1, the truth ness of 𝑆(𝑛) for 𝑛 = 𝑘 + 1 is established.
𝑛(2𝑛−1)(2𝑛+1)
6. Prove, by mathematical induction that 12 + 32 + 52 + ⋯ ⋯ ⋯ + (2𝑛 − 1)2 = for all
3
integers 𝑛 ≥ 1.
Solution:

Let S(n) denote the given statement.

Basic step: We note that is 𝑆(1) is the statement

1
12 = ∙ 1 ∙ (2 − 1) ∙ (2 + 1) which is clearly true.
3

Induction Step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we
assume that the following statement is true.
𝑘(2𝑘−1)(2𝑘+1)
𝑆(𝑘) = 12 + 32 + 52 + ⋯ ⋯ ⋯ + (2𝑘 − 1)2 = .
3

Adding (2𝑘 + 1)2 to both sides of this, we obtain

𝑘(2𝑘−1)(2𝑘+1)
𝑆(𝑘) = 12 + 32 + 52 + ⋯ ⋯ ⋯ + (2𝑘 − 1)2 + (2𝑘 + 1)2 = + (2𝑘 + 1)2
3
𝑘 (2𝑘−1)
= (2𝑘 + 1) { + (2𝑘 + 1)}
3
1
= ((2𝑘 + 1){𝑘(2𝑘 − 1) + 3(2𝑘 + 1)}
3
1
= ((2𝑘 + 1){2𝑘2 − 𝑘 + 6𝑘 + 3}
3
1
= ((2𝑘 + 1){2𝑘2 + 5𝑘 + 3}
3
1
= (2𝑘 + 1)(𝑘 + 2)(2𝑘 + 3)
3

This is precisely the statement 𝑆(𝑘 + 1). Thus, on the basis of the assumption that 𝑆(𝑛) is true for 𝑛 = 𝑘 ≥
1, the truth ness of 𝑆(𝑛) for 𝑛 = 𝑘 + 1 is established.

7. Prove by mathematical induction that, for all positive integers 𝑛 ≥ 1.

1
1 ∙ 3 + 2 ∙ 4 + 3 ∙ 5 + ⋯ ⋯ ⋯ + 𝑛(𝑛 + 2) = 𝑛(𝑛 + 1)(2𝑛 + 7)
6

Solution:

Here, we have to prove the statement

1
𝑆(𝑛) = 1 ∙ 3 + 2 ∙ 4 + 3 ∙ 5 + ⋯ ⋯ ⋯ + 𝑛(𝑛 + 2) = 𝑛(𝑛 + 1)(2𝑛 + 7) for all integers 𝑛 ≥ 1.
6

Basic step: We note that 𝑆(1) is the statement

1
1 ∙ 3 = ∙ 1 ∙ (1 + 1) ∙ (2 + 7)
6

Which is clearly true. thus, the statement 𝑆(𝑛)is verified for 𝑛 = 1.

Induction step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we

assume that the following statement is true:

 1
𝑆(𝑘) = 1 ∙ 3 + 2 ∙ 4 + 3 ∙ 5 + ⋯ ⋯ ⋯ + 𝑘(𝑘 + 2) = 𝑘(𝑘 + 1)(2𝑘 + 7)
6

Using this we find that (by adding (𝑘 + 1)(𝑘 + 3) to both side)

1
𝑆(𝑘) = 1 ∙ 2 + 2 ∙ 3 + 3 ∙ 4 + ⋯ ⋯ ⋯ + 𝑘(𝑘 + 2) + (𝑘 + 1)(𝑘 + 3) = 𝑘(𝑘 + 1)(2𝑘 + 7) + (𝑘 +
6
1)(𝑘 + 3)
1
= (𝑘 + 1) { 𝑘(2𝑘 + 7) + (𝑘 + 3)}
6

= (𝑘 + 1){2𝑘2 + 7𝑘 + 6𝑘 + 18}

= (𝑘 + 1){2𝑘2 + 13𝑘 + 18}

1
= (𝑘 + 1)(𝑘 + 2)(2𝑘 + 9)
6

This is precisely the statement 𝑆(𝑘 + 1). Thus, on the basis of the assumption that 𝑆(𝑛) is true for 𝑛 = 𝑘 ≥
1, the truth ness of 𝑆(𝑛) for 𝑛 = 𝑘 + 1 is established.

8. Prove that every positive integer greater than or equal to 14 can be written as a sum of 3’s and/or 8’s.

Solution:

Basic step: We note that 14 = (3 + 3) + 8

This shows 𝑆(14) is true.

Induction step: We assume that 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 ≥ 14. Then

𝑘 = (3 + 3 + ⋯ ⋯ ) + (8 + ⋯ ⋯ )

Suppose this representation of 𝑘 has 𝑟 number of 3’s and 𝑠 number of 8’s. Since 𝑘 ≥ 14 we should have
𝑟 ≥ 2 and 𝑠 ≥ 2.

Using this representation of 𝑘, we find that

𝑘 + 1 = {⏟
(3 + 3_ (8_+ ⋯ ⋯¸)} + 1
+_⋯ ⋯¸) + ⏟
𝑟 𝑠

= {(⏟3_+ 3_+ ⋯_⋯ (8_+ ⋯ ⋯¸) + 8} + 1

¸) + ⏟
𝑟 𝑠−1

= {(⏟3 + 3_ ( 8_+ ⋯ ⋯¸)}

+_⋯ ⋯¸) + ⏟
𝑟+3 𝑠−1

This shows that 𝑘 + 1is sum of 3’s and 8’s. Thus, 𝑆(𝑘 + 1) is true.

9. Prove by mathematical induction for any integer 𝑛 ≥ 1

1 1 1 𝑛
+ + ⋯⋯⋯+ = 6𝑛+4
2∙5 5∙8 (3𝑛−1)(3𝑛+2)
Solution:

Here, we have to prove the statement

1 1 1 𝑛
𝑆(𝑛) = + + ⋯ ⋯ ⋯ + (3𝑛−1)(3𝑛+2) = 6𝑛+4 for all integers 𝑛 ≥ 1.
2∙5 5∙8

Basic step: We note that 𝑆(1) is the statement

1 1
= 6∙1+4
2∙5

Which is clearly true. thus, the statement 𝑆(𝑛)is verified for 𝑛 = 1.

Induction step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we

assume that the following statement is true:

1 1 1 𝑘
𝑆(𝑘) = + + ⋯⋯⋯+ = 6𝑘+4
2∙5 5∙8 (3𝑘−1)(3𝑘+2)

Using this we find that (by adding 1

to both side)
(3𝑘+2)(3𝑘+5)

1 1 1 1 𝑘 1
𝑆(𝑘) = + + ⋯⋯ ⋯+ + = 6𝑘+4 +
2∙5 5∙8 (3𝑘−1)(3𝑘+2) (3𝑘+2)(3𝑘+5) (3𝑘+2)(3𝑘+5)

𝑘(3𝑘+2)(3𝑘+5)+(6𝑘+4)
= (6𝑘+4)(3𝑘+2)(3𝑘+5)

9𝑘3+21𝑘2+16𝑘+4
= (6𝑘+4)(3𝑘+2)(3𝑘+5)

(𝑘−1)(3𝑘+2)2
= (6𝑘+4)(3𝑘+2)(3𝑘+5)

(𝑘+1)(3𝑘+2)
=
(6𝑘+4)(3𝑘+5)

This is precisely the statement 𝑆(𝑘 + 1). Thus, on the basis of the assumption that 𝑆(𝑛) is true for 𝑛 = 𝑘 ≥
1, the truth ness of 𝑆(𝑛) for 𝑛 = 𝑘 + 1 is established.

10. Prove by mathematical induction that, for every positive integer 𝑛, 5 divides 𝑛5 − 𝑛

Solution:

Let 𝑆(𝑛) be the given statement.

Basic step: We note that 𝑆(1) is the statement

5 divides 15 − 1

Since 15 − 1 = 0, this statement is true

Induction step: We assume that the statement 𝑆(𝑛) is true for 𝑛 = 𝑘 where 𝑘 is an integer ≥ 1; that is, we

assume that the following statement is true:

5 divides 𝑘5 − 𝑘,

This means that 𝑘5 − 𝑘 is a multiple of 5; that is 𝑘5 − 𝑘 = 5𝑚, for some positive integer m.

Consequently, we find that

(𝑘 + 1)5 − (𝑘 + 1) = (𝑘5 + 5𝑘4 + 10𝑘3 + 10𝑘2 + 5𝑘 + 1) − (𝑘 + 1)

= (𝑘5 − 𝑘) + 5(𝑘4 + 2𝑘3 + 2𝑘2 + 𝑘)

= 5𝑚 + 5(𝑘4 + 2𝑘3 + 2𝑘2 + 𝑘)

= 5(𝑚 + 𝑘4 + 2𝑘3 + 2𝑘2 + 𝑘)

This shows that (𝑘 + 1)5 − (𝑘 + 1) is a multiple of 5; that is, 5 divides (𝑘 + 1)5 − (𝑘 + 1).

This is precisely the statement 𝑆(𝑛) for 𝑛 = 𝑘 + 1. Thus, on the assumption that 𝑆(𝑛)is true for 𝑛 = 𝑘 ≥ 1,
We have proved that 𝑆(𝑛) is true for 𝑛 = 𝑘 + 1.
☻Recursive Definition:

For describing a sequence, the two methods are commonly used.

(i) Explicit method (ii) Recursive method

In explicit method, the general term of the sequence is explicitly indicated

In recursive method, first few terms of the sequence must be indicated explicitly and in the second part the
rule which will enable us to obtain new term if the sequence from the terms already known must be indicated.

Problems:

1. Find an explicit definition of the sequence defined recursively by

𝑎1 = 7, 𝑎𝑛 = 2𝑎𝑛−1 + 1 for 𝑛 ≥ 2.

Solution: By repeated use of the given recursive definition we find that

𝑎𝑛 = 2𝑎𝑛−1 + 1 = 2{2𝑎𝑛−2 + 1} + 1

= 2{2(2𝑎𝑛−3 + 1) + 1} + 1 = 23𝑎𝑛−3 + 22 + 2 + 1

⋯⋯⋯

⋯⋯⋯

= 2𝑛−1𝑎𝑛−(𝑛−1) + 2𝑛−2 + 2𝑛−3 + ⋯ ⋯ + 22 + 2 + 1

= 2𝑛−1𝑎1 + (1 + 2 + 22 + 23 + ⋯ ⋯ + 2𝑛−3 + 2𝑛−2)

Using 𝑎1 = 7 and the standard result

𝑎𝑛−1
1 + 𝑎 + 𝑎2 + 𝑎3 + ⋯ ⋯ + 𝑎𝑛−1 = for 𝑎 > 1
𝑎−1

2𝑛−1 −1
This becomes 𝑎𝑛 = 7 ∙ 2𝑛−1 + = 8 ∙ 2𝑛−1 − 1
2−1

2. Obtain the recursive definition for the sequence {𝑎𝑛} is each of the following cases.

(𝑖). 𝑎𝑛 = 5𝑛 (𝑖𝑖). 𝑎𝑛 = 6𝑛 (𝑖𝑖𝑖). 𝑎𝑛 = 3𝑛 + 7

(𝑖𝑣). 𝑎𝑛 = 𝑛(𝑛 + 2) (𝑣). 𝑎𝑛 = 𝑛2 (𝑣𝑖). 𝑎𝑛 = 2 − (−1)𝑛

Solution:

(i). Here 𝑎1 = 5, 𝑎2 = 10, 𝑎3 = 15, 𝑎4 = 20, … … …

We can rewrite these as 𝑎1 = 5 and 𝑎𝑛 = 𝑎𝑛−1 + 5 for 𝑛 ≥ 2.

This is the Recursive definition of the given sequence.

(ii). Here 𝑎1 = 6, 𝑎2 = 62, 𝑎3 = 63, 𝑎4 = 64, … … …

We can rewrite these as 𝑎1 = 6 and 𝑎𝑛+1 = 6𝑎𝑛 for 𝑛 ≥ 1.

This is the Recursive definition of the given sequence.

(iii). Here 𝑎1 = 10, 𝑎2 = 13, 𝑎3 = 16, 𝑎4 = 19, … … …

We can rewrite these as 𝑎1 = 10 and 𝑎𝑛 = 𝑎𝑛−1 + 3 for 𝑛 ≥ 2.

This is the Recursive definition of the given sequence.

(iv). Here 𝑎1 = 3, 𝑎2 = 8, 𝑎3 = 15, 𝑎4 = 24, … … …

We observe that 𝑎2 − 𝑎1 = 5 = 2 ∙ 1 + 3, 𝑎3 − 𝑎2 = 7 = 2 ∙ 2 + 3, 𝑎4 − 𝑎3 = 9 = 2 ∙ 3 + 3

We can rewrite these as 𝑎𝑛+1 − 𝑎𝑛 = 2𝑛 + 3 then 𝑎𝑛+1 = 𝑎𝑛 + 2𝑛 + 3 for 𝑛 ≥ 1.

Hence 𝑎1 = 3 and 𝑎𝑛+1 = 𝑎𝑛 + 2𝑛 + 3 for 𝑛 ≥ 1.

This is the Recursive definition of the given sequence.

(v). Here 𝑎1 = 1, 𝑎2 = 4, 𝑎3 = 9, 𝑎4 = 16, … … …

We observe that 𝑎2 − 𝑎1 = 3 = 2 ∙ 1 + 1, 𝑎3 − 𝑎2 = 5 = 2 ∙ 2 + 1, 𝑎4 − 𝑎3 = 7 = 2 ∙ 3 + 1

We can rewrite these as 𝑎𝑛+1 − 𝑎𝑛 = 2𝑛 + 1 then 𝑎𝑛+1 = 𝑎𝑛 + 2𝑛 + 1 for 𝑛 ≥ 1.

Hence 𝑎1 = 1 and 𝑎𝑛+1 = 𝑎𝑛 + 2𝑛 + 1 for 𝑛 ≥ 1.

This is the Recursive definition of the given sequence.

(vi). Here 𝑎1 = 3, 𝑎2 = 1, 𝑎3 = 3, 𝑎4 = 1, … … …

We observe that 𝑎2 − 𝑎1 = −2 = 2 (−1), 𝑎3 − 𝑎2 = 2 = 2(1), 𝑎4 − 𝑎3 = −2 = 2(−1)

We can rewrite these as 𝑎𝑛+1 − 𝑎𝑛 = 2(−1)𝑛 then 𝑎𝑛+1 = 𝑎𝑛 + 2(−1)𝑛

Hence 𝑎1 = 3 and 𝑎𝑛+1 = 𝑎𝑛 + 2(−1)𝑛 for 𝑛 ≥ 1.

This is the Recursive definition of the given sequence.

3. The Fibonacci numbers are defined recursively by 𝐹0 = 0, 𝐹1 = 1 and 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 for 𝑛 ≥ 2
Evaluate 𝐹2 to 𝐹10

Solution:

Given 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 for 𝑛 ≥ 2

𝐹2 = 𝐹1 + 𝐹0 = 1 + 0 = 1

𝐹3 = 𝐹2 + 𝐹1 = 1 + 1 = 2

𝐹4 = 𝐹3 + 𝐹2 = 2 + 1 = 3
𝐹5 = 𝐹4 + 𝐹3 = 3 + 2 = 5

𝐹6 = 𝐹5 + 𝐹4 = 5 + 3 = 8

𝐹7 = 𝐹6 + 𝐹5 = 8 + 5 = 13

𝐹8 = 𝐹7 + 𝐹6 = 13 + 8 = 21

𝐹9 = 𝐹8 + 𝐹7 = 21 + 13 = 34

𝐹10 = 𝐹9 + 𝐹8 = 34 + 21 = 55

Note: The Sequence formed by the Fibonacci numbers is called the Fibonacci sequence.

4. The Lucas numbers are defined recursively by 𝐿0 = 2, 𝐿1 = 1 and 𝐿𝑛 = 𝐿𝑛−1 + 𝐿𝑛−2 for 𝑛 ≥ 2

Evaluate 𝐿2 to 𝐿10

Solution:

Given 𝐿𝑛 = 𝐿𝑛−1 + 𝐿𝑛−2 for 𝑛 ≥ 2

𝐿2 = 𝐿1 + 𝐿0 = 1 + 2 = 3

𝐿3 = 𝐿2 + 𝐿1 = 3 + 1 = 4

𝐿4 = 𝐿3 + 𝐿2 = 4 + 3 = 7

𝐿5 = 𝐿4 + 𝐿3 = 7 + 4 = 11

𝐿6 = 𝐿5 + 𝐿4 = 11 + 7 = 18

𝐿7 = 𝐿6 + 𝐿5 = 18 + 11 = 29

𝐿8 = 𝐿7 + 𝐿6 = 29 + 18 = 47

𝐿9 = 𝐿8 + 𝐿7 = 47 + 29 = 76

𝐿10 = 𝐿9 + 𝐿8 = 76 + 47 = 123

Note: The Sequence formed by the Lucas numbers is called the Lucas sequence.
1 𝑛 𝑛
1−√5
5. For the Fibonacci sequence 𝐹0, 𝐹1, 𝐹2, … … … …. Prove that 𝐹𝑛 = [( 1+√5) − ( )]
√5 2 2

Solution:

For 𝑛 = 0 and 𝑛 = 1, the required results read (respectively)

0 0
1 1
𝐹0 = [( 1+√5) − (1−√5) ] = [1 − 1] = 0
√5 2 2 √5
1 1+√ 5 1−√ 5 1
𝐹= [( )−( )] = [√5] = 1
1 2 2 √5
√5
Which is true.

Thus, the required result is true for 𝑛 = 0 and 𝑛 = 1. We assume that the result is true for 𝑛 = 0, 1, 2, … . 𝑘,
where 𝑘 ≥ 1. Then, we find that

𝐹𝑘+1 = 𝐹𝑘 + 𝐹𝑘−1
𝑘
1+√5 1−√5 𝑘 1 𝑘−1 𝑘−1
𝐹𝑘+1 = 1 [( ) −( ) ]+ [(1+√5 ) −(
1−√5 ) ] using the assumption made
√5 2 2 √5 2 2

1 1+√5 𝑘−1 1+√5 1−√5 𝑘−1 1−√5

𝐹𝑘+1 = [( ) { + 1} − ( ) { + 1}]
√5 2 2 2 2

1 1+√5 𝑘−1 3+√5 1−√5 𝑘−1 3−√5

𝐹𝑘+1 = [( ) { }−( ) { }]
√5 2 2 2 2

1 1+√5 𝑘−1 6+2√5 1−√5 𝑘−1 6−2√5

𝐹𝑘+1 = [( ) { }−( ) { }]
√5 2 4 2 4

1 𝑘+1 𝑘+1
𝐹𝑘+1 = [( 1+√5) −(
1−√5
) ]
√5 2 2

This shows that the required result is true for 𝑛 = 𝑘 + 1. Hence by mathematical induction, the result is true
for all non – negative integers n.
☻The Rules of Sum and Product:

Rule of sum:

Suppose two tasks 𝑇1 and 𝑇2 are to be performed. if the task 𝑇1 can be performed in m different ways and the
task 𝑇2 can be performed in n different ways and if these two tasks cannot be performed simultaneously, then
one of the two tasks (𝑇1 or 𝑇2) can be performed in 𝑚 + 𝑛 ways.

Example: Suppose 𝑇 1 is the task of selecting a prime no. < 10 and 𝑇 2 is the task of selecting an even number
< 10. then 𝑇1 can be performed in 4 ways and 𝑇2 can be performed in 4 ways. But since 2 is both a prime and
an even number < 10 the task T1 or 𝑇2 can be performed in 4 + 4 – 1 = 7 ways.

Rule of product:

Suppose two tasks are to be performed one after the other. If 𝑇1 can be performed in 𝑛1 different ways, and
for each of these ways 𝑇2 can be performed in 𝑛2different ways. then both of the tasks can be performed in
𝑛1 ∗ 𝑛2 different ways.

Example: Suppose a person has 8 shirts and 5 ties. Then He has 8 * 4 = 40 different ways of choosing a shirt
and a tie.

Problems:

1. Cars of a particular manufacturer come in 4 models, 12 colours, 3 engine sizes and 2 transmission
types (a) how many distinct cars can be manufactured? (b) of these how many have the same colour?

Solution:

(a) By the product rule, it follows that the number of distinct cars that can be manufactured is 4*12*3*2 =288

(b) for any chosen colour, the number of distinct cars that can be manufactured is 4*3*2=24

2. A bit is either 0 or 1. A byte is a sequence of 8 bits. Find (i) the number of bytes. (ii) the number of
bytes that begin with 11 and end with 11. (iii) The number of bytes that begin with 11 and do not end
with 11. (iv) the number of bytes that begin with 11 or end with 11.

Solution:

(i) Since each byte contains 8 bits and each bit is 0 or 1, the number of bytes is 28 = 256

(ii) In a byte beginning and ending with 11, there occur 4 open positions. These can be filled un 24 = 16 ways.
Therefore, there are 16 bytes which begin and end with 11.

(iii) These occur 6 open positions in a byte beginning with 11. these positions can be filled is 2 6 = 64 ways.
thus, there are 64 bytes that begin with 11. since there are 16 bytes that begin and end with 11, the number
of bytes that begin with 11 but do not end with 11 is 64-16 = 48.

(iv) As in (iii) the numbers of bytes that end with 11 is 64. Also, the number of bytes that begin and end with
11 is 16. Therefore, the number of bytes that begin or end with 11 is 64 + 64 = 16 = 112.

3. Find the number of 3 digit even numbers with no repeated digits.

Solution:

Here we consider number of the form 𝑥 𝑦 𝑧, where each of 𝑥, 𝑦, 𝑧 represents a digit under the given
restrictions. Since 𝑥 𝑦 𝑧 has to be even, z has to be 0, 2, 4, 6 or 8. If 𝑧 is 0, then 𝑥 has 9 choices and 𝑦 𝑧 has
2, 4, 6, 8 (4 choices) then 𝑥 has 8 choices (Note that 𝑥 cannot be 0). Therefore, 𝑧 and 𝑥 can be chosen in
1 × 9 + 4 × 8 = 41 ways. For each of these ways, 𝑦 can be chosen in 8 ways.

Hence, the desired number is 41 * 8 = 328.

4. Find the number of proper divisors of 441000.

Solution:

We note that 441000 = 23 × 32 × 53 × 72. Therefore, every divisor of 𝑛 = 441000 must be of the form
𝑑 = 2𝑝 × 3𝑞 × 5𝑟 × 7𝑠 where 0 ≤ 𝑝 ≤ 3, 0 ≤ 𝑞 ≤ 2, 0 ≤ 𝑟 ≤ 3, 0 ≤ 𝑠 ≤ 2.

Thus, for a divisor d, p can be chosen in 4 ways, q in 3 ways, r in 4 ways and s in 3 ways. Accordingly, the
number of possible d’s is 4 × 3 × 4 × 3 = 144. Of these, two divisors (namely 1 and 𝑛) are not proper
divisors. Therefore, the number of proper divisors of the given number is 144 − 2 = 142.

5. How many among the first 100,000 positive integers contain exactly one 3, one 4 and one 5 in their
decimal representations?

Solution:

The number 100000 does not contain 3 or 4 or 5. Therefore, we have to consider all possible positive integers
with 5 places that meet the given conditions. In a 5-place integer the digit 3 can be in any one of the 5 places.
Subsequently, the digit 4 can be in any one of the 4 remaining places. Then the digit 5 can be in any one of
the 3 remaining places. There are 2 places left and either of these may be filled by 5 digits (digits from 0 to
9 other tan 3, 4, 5). Thus, there are 5 × 4 × 3 × 7 × 7 = 2940 integers of the required type.
☻Permutations:

Suppose that we are given 𝑛 distinct objects and wish to arrange r of these objects in a line. Since there are
𝑛 ways of choosing the first object, and after this done 𝑛 − 1 ways of choosing the second object…. And
finally, 𝑛 − 𝑟 + 1 ways of choosing 𝑟𝑡ℎ object, it follows by the product rule of counting (stated in the
preceding section) that the number of different arrangements, or permutations (as they are commonly called)
is 𝑛(𝑛 − 1)(𝑛 − 2) ⋯ ⋯ ⋯ (𝑛 − 𝑟 + 1). We denote this number by 𝑃(𝑛, 𝑟) and is referred to as the number
of permutations of size 𝑟 of 𝑛 objects.

𝒏!
𝑷(𝒏, 𝒓) =
(𝒏 − 𝒓)!

Generalization

Suppose it is required to find the number of permutations that can be formed from a collection of 𝑛 objects
of which 𝑛1 are of one type , 𝑛 2 are of a second type ,……… 𝑛𝑘 are of 𝑘𝑡ℎ type, with 𝑛1 + 𝑛2 + ⋯ ⋯ +
𝑛𝑘 = 𝑛. Then, the number of permutations of the objects is

𝒏!
𝒏𝟏! 𝒏𝟐! ⋯ ⋯ 𝒏𝒌!

Problems:

1. Four different mathematics books, five different computer science books and two different control
theory books are to be arranged in a shelf. How many different arrangements are possible if (a) The
books in each particular subject must be together? (b) Only mathematics books must be together?

Solution:

(a) The mathematics books can be arranged among themselves in 4! Ways, the computer science books in
5! Ways the control theory books in 2! Ways, and the three groups in 3! Ways. Therefore, the number of
possible arrangements is 4! * 5! * 2! * 3! = 34560.

(b) Consider the 4 mathematics boos as one single book. Then we have 8 books which can be arranged in 8!
Ways. In all of these ways the mathematics books are together. But the mathematics books can be arranged
among themselves in 4! Ways. Hence, the number of arrangements is 8! * 4! = 967680

2. Find the number of permutations of the letters of the word MASSASAUGA. In how many of these,
all four ‘A’s are together? How many of them begin with S?

Solution:

The given word has 10 letters of which 4 are A, 3 are S and 1 each are M, U and G. Therefore, the required
number of permutations is
10!
= 25200
4! ∗ 3! ∗ 1! ∗ 1! ∗ 1!
It is a permutation all A’s are to be together, we treat all of A’s as one single letter. Then the letters to be
permuted read (AAAA), S, S, S, M, U, G (which are 7 in number) and the number of permutations is
 7!
= 840
1! ∗ 3! ∗ 1! ∗ 1! ∗ 1!

For permutations beginning with S, there occur nine open positions to fill, where two are S, four are A, and
one each of M, U, G. The number of such permutations is
9!
= 7560
2! ∗ 4! ∗ 1! ∗ 1! ∗ 1!

3. (a) How many arrangements are there for all letters in the word SOCIOLOGICAL?

(b) In how many of these arrangements (i) A and G are adjacent? (ii) all the vowels are adjacent?

Solution:

(a) The given word has 12 letters of which three are O, two each are C, I, L and one each are S, A, G.
Therefore, the number of arrangements of these letters is

12!
= 25200
3! ∗ 2! ∗ 2! ∗ 2! ∗ 1! ∗ 1! ∗ 1!

(b)

(i) If, in an arrangement, A and G are to be adjacent, we treat A and G together as a single letter, say X so
that we have three numbers of O’s, two each of C, L, I and one each of S and X, totalling 11 letters. These
can be arranged in 11!
Ways
3!∗2!∗2!∗2!∗1!

Further the letters A and G can be arranged among themselves in two ways.

Therefore, the total number of arrangements in this case is

11!
× 2 = 1663200
3! ∗ 2! ∗ 2! ∗ 2! ∗ 1!
(ii) If, in an arrangement, all the vowels are to be adjacent, we treat all the vowels present in the given word
(A, O, I) as a single letter, say Y, so that we have two each of C and L and one each of S, G & Y totalling to
7 letters. These can be arranged in 7!
ways
2!∗2!∗1!∗1!∗1!

Further, since the given words contains 3 O’s, two I’s and one A, the letters A, O, I (clubbed as Y) can be
arranged among themselves is 6! Ways.
3!∗2!∗1!

7! 6!
Therefore, the total number of arrangements in this case is × = 75600
2!∗2!∗1!∗1!∗1! 3!∗2!∗1!

4. How many Positive integers n can we form using the digits 3, 4, 4, 5, 5, 6, 7 if we want n to exceed
5,000,000?

Solution:
Here n must be of the form 𝑛 = 𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7

Where 𝑥1, 𝑥2, … … , 𝑥7 are the given digits with 𝑥1 = 5, 6 𝑜𝑟 7. Suppose we take 𝑥1 = 5. Then where
𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7 is an arrangement of the remaining 6 digits which contains two 4’s and one each of 3, 5, 6, 7.
The number of such arrangements is
6!
= 360
1! 2! 1! 1! 1!

Similarly, we take 𝑥1 = 6. Then where 𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7 is an arrangement of the remaining 6 digits which
contains two each of 4 & 5 and one each of 3 & 7. The number of such arrangements is
6!
= 180
1! 2! 2! 1!

Similarly, we take 𝑥1 = 7. Then where 𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7 is an arrangement of the remaining 6 digits which
contains two each of 4 & 5 and one each of 3 & 6. The number of such arrangements is
6!
= 180
1! 2! 2! 1!

Accordingly, by the Sum Rule, the number of 𝑛’s of the desired type is 360 + 180 + 180 = 720.

5. How many numbers greater than 1,000,000 can be formed by using the digits 1, 2, 2, 2, 4, 4, 0?

Solution:

Here n must be of the form 𝑛 = 𝑥1𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7

Where 𝑥1, 𝑥2, … … , 𝑥7 are the given digits with 𝑥1 = 1, 2 𝑜𝑟 4. Suppose we take 𝑥1 = 1. Then where
𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7 is an arrangement of the remaining 6 digits which contains three 2’s and two 4’s. The number
of such arrangements is
6!
= 60
3! 2!

Similarly, we take 𝑥1 = 2. Then where 𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7 is an arrangement of the remaining 6 digits which
contains two 2’s and two 4’s. The number of such arrangements is
6!
= 180
2! 2!
Similarly, we take 𝑥1 = 4. Then where 𝑥2𝑥3𝑥4𝑥5𝑥6𝑥7 is an arrangement of the remaining 6 digits which
contains three 2’s and one 4. The number of such arrangements is
6!
= 120
3! 1!
Accordingly, by the Sum Rule, the number of 𝑛’s of the desired type is 60 + 180 + 120 = 360.
☻Combinations:

Suppose we are interested in selecting (choosing) a set of 𝑟 objects from a set of 𝑛 ≥ 𝑟 objects without regard
to order. The set of 𝑟 objects being selected is traditionally called a Combination of 𝑟 objects (or briefly 𝑟-
combination).

The total number of combinations of 𝑟-different objects that can be selected from 𝑛 different objects can be
obtained by proceeding in the following way. Suppose this number is equal to 𝐶, say; that is, suppose there
is a total of 𝐶 number of combinations of 𝑟 different objects chosen from 𝑛 different objects. Take any one
of these combinations. The 𝑟 objects in this combination can be arranged in 𝑟! Different ways. Since there
are 𝐶 combinations, the total number of permutations is 𝐶 ∙ 𝑟!. But this is equal to 𝑃(𝑛, 𝑟). Thus,
𝑷(𝒏,𝒓) 𝒏!
𝑪(𝒏, 𝒓) = = for 𝟎 ≤ 𝒓 ≤ 𝒏
𝒓! (𝒏−𝒓)! 𝒓!

Problems:

1. A certain question paper contains two parts A and B each containing 4 questions. How many different
ways a student can answer 5 questions by selecting at least 2 questions from each part?

Solution: The different ways a student can select his 5 questions are.

(i) 3 questions from part A and 2 questions from part B. this can be done in 𝐶(4, 3) ∗ 𝐶(4, 2) = 24 ways.

(ii) 2 questions from part A and 3 questions from part B. this can be done in 𝐶(4, 2) ∗ 𝐶(4, 3) = 24 ways.

Therefore, the total number of ways a student can answer 5 questions under given restrictions is 24 + 24 =
48.

2. Prove the following identities.

𝐶(𝑛, 𝑟 − 1) + 𝐶(𝑛, 𝑟) = 𝐶(𝑛 + 1, 𝑟)

𝐶(𝑚, 2) + 𝐶(𝑛, 2) = 𝐶(𝑚 + 𝑛, 2) − 𝑚𝑛

Proof:
𝑛! 𝑛!
(i). 𝐶(𝑛, 𝑟 − 1) + 𝐶(𝑛, 𝑟) = +
(𝑟−1)! (𝑛−𝑟+1)! 𝑟! (𝑛−𝑟)!

𝑛! 1 1
= { + }
(𝑟−1)! (𝑛−𝑟)! 𝑛−𝑟+1 𝑟

𝑛! 𝑛+1
= ∙
(𝑟−1)! (𝑛−𝑟)! 𝑟 (𝑛−𝑟+1)

(𝑛+1)!
=
𝑟! (𝑛−𝑟+1)!

= 𝐶(𝑛 + 1, 𝑟)
𝑚! 𝑛!
(ii). 𝐶(𝑚, 2) + 𝐶(𝑛, 2) = +
(𝑚−2)! ∙ 2 (𝑛−2)! ∙2

1
= {𝑚(𝑚 − 1) + 𝑛(𝑛 − 1)}
2
 1
= {𝑚2 + 𝑛 2 − 𝑚 − 𝑛}
2
1
= (𝑚 + 𝑛)(𝑚 + 𝑛 − 1) − 𝑚𝑛
2

(𝑚+𝑛)!
= − 𝑚𝑛
2 (𝑚+𝑛−2)!

= 𝐶(𝑚 + 𝑛, 2) − 𝑚𝑛

3. A woman has 11 close relatives and she wishes to invite 5 of them to dinner. In how many ways can
she invite them in the following situations:
(i). There is no restriction on the choice.
(ii). Two particular persons will not attend separately.
(iii). Two particular persons will not attend together.

Solution:

(i). Since there is no restriction on the choice of invitees, five out of 11 can be invited in
11!
𝐶(11, 5) = = 462 ways
6! 5!

(ii). Since two particular persons will not attend separately, they should both be invited or not invited.

Suppose if both of them are invited, then three are more invitees are to be selected from the remaining 9
relatives. This can be done in
9!
𝐶(9, 3) = = 84 ways
6! 3!

Suppose if both of them are not invited, then five invitees are to be selected from the remaining 9 relatives.
This can be done in
9!
𝐶(9, 5) = = 126 ways
5! 4!

Therefore, the total number of ways in which the invitees can be selected in this case is 84 + 126 = 210.

(iii). Since two particular persons (Say 𝑃1 & 𝑃2) will not attend together, only one of them can be invited or
none of them can be invited. The number of ways of choosing the invitees with 𝑃1 invited is
9!
𝐶(9, 4) = = 126 ways
5! 4!

Similarly, the number of ways of choosing the invitees with 𝑃2 invited is 126 ways

If both 𝑃1 & 𝑃2 are not invited, then the number of ways of inviting the invitees is
9!
𝐶(9, 5) = = 126 ways
5! 4!

Therefore, the total number of ways in which the invitees can be selected in this case is
 126 + 126 + 126 = 378.

4. Find the number of arrangements of all the letters in TALLAHASSEE. How many of these
arrangements have no adjacent A’s?

Solution:

The number of letters in the given word is 11 of which 3 are A’s, 2 each are L’s, S’s, E’s and 1 each are T
and H. Therefore, the number of arrangements (permutations) of the letters in the given word is
11!
= 831600
3! 2! 2! 2! 1! 1!

If we disregard the A’s, the remaining 8 letters can be arranged in

8!
= 5040
2! 2! 2! 1! 1!

In each of these arrangements, there are 9 possible locations for the three A’s. These locations can be chosen
in 𝐶(9, 3) ways. Therefore, the number of arrangements having no adjacent A’s is

9!
5040 × 𝐶(9, 3) = 5040 × = 5040 × 84 = 423360
3! 6!
5. A committee of 12 is to be selected from 10 men and 10 women. In how many ways can the selection
be carried out if
(a) there are no restrictions?
(b) there must be six men and six women?
(c) there must be an even number of women?
(d) there must be more women than men?
(e) there must be at least eight men?

Solution:

(a). If there is no restriction than it is a simple selection of 12 out of 20.

20!
𝐶(20, 12) = = 125970
12! 8!
(b). For 6 men out of 10 and 6 women out of 10. These are two different stages of selection that's why product
rule is used
10! 10!
𝐶(10, 6) × 𝐶(10, 6) = × = 44100
6! 4! 6! 4!
(c). 2, 4, 6, 8 or 10 can be the number of women in committee and corresponding to that men will be 10, 8,
6, 4 and 2.

𝐶(10, 2) × 𝐶(10, 10) + 𝐶(10, 4) × 𝐶(10, 8) + 𝐶(10, 6) × 𝐶(10, 6) + 𝐶(10, 8) × 𝐶(10, 4) + 𝐶(10, 10) ×
𝐶(10, 2) = 63090

(d). Number of women can be 7, 8, 9 or 10 and number of men will be 5, 4, 3, 2 respectively.

𝐶(10, 7) × 𝐶(10, 5) + 𝐶(10, 8) × 𝐶(10, 4) + 𝐶(10, 9) × 𝐶(10, 3) + 𝐶(10, 10) × 𝐶(10, 2) = 40935

(e). Number of men can be 8, 9 or 10 in this case and respectively number of women can be 4, 3 and 2.

𝐶(10, 8) × 𝐶(10, 4) + 𝐶(10, 9) × 𝐶(10, 3) + 𝐶(10, 10) × 𝐶(10, 2) = 10695

☻Binomial and Multinomial Theorems:

Binomial Theorem:
𝑛
On the basic properties of 𝐶(𝑛, 𝑟) = ( ) is that it is the coefficient of 𝑥𝑟𝑦𝑛−𝑟 and 𝑥𝑛−𝑟𝑦𝑟 in the expansion
𝑟
of the expression (𝑥 + 𝑦)𝑛, where 𝑥 and 𝑦 are real numbers. In other words,
(𝑥 + 𝑦)𝑛 = ∑𝑛 𝑛 𝑛 𝑟−𝑛𝑦𝑟
𝑟 𝑛−𝑟 = ∑ 𝑛
𝑟=0 ( ) 𝑥 𝑦 (
𝑟=0 𝑟 ) 𝑥
𝑟
This result is known as the binomial theorem for a positive integral index.

Multinomial Theorem:
For positive integers n and k the coefficient of 𝑥𝑛1 𝑥𝑛2 𝑥𝑛3 … … . . 𝑥𝑛𝑘 in the expansion of
1 2 3 𝑘
(𝑥1 + 𝑥2 + 𝑥3 + ⋯ ⋯ ⋯ + 𝑥𝑘 )𝑛 is 𝑛!
𝑛1! 𝑛2! 𝑛3!……𝑛 𝑘!

Problems:

1. Find the coefficient of

(i) 𝑥 9𝑦 3 in the expansion of (2𝑥 − 3𝑦)12

(ii) 𝑥12 in the expansion of 𝑥3(1 − 2𝑥)10

2 15
(iii) 𝑥0 in the expansion of (3𝑥2 − )
𝑥

Solution:
By the Binomial theorem, we have (𝑥 + 𝑦)𝑛 = ∑𝑛 𝑛 𝑟 𝑛−𝑟 = ∑𝑛 𝑛 𝑟−𝑛 𝑟
𝑦
𝑟=0 ( ) 𝑥 𝑦 𝑟=0 ( ) 𝑥
𝑟 𝑟
12
(i). (2𝑥 − 3𝑦)12 = ∑12 𝑟 12−𝑟
𝑟=0 ( ) (2𝑥) (−3𝑦)
𝑟
12 𝑟( )12−𝑟 𝑟 12−𝑟
= ∑12 𝑥 𝑦
𝑟=0 ( ) 2 −3
𝑟
In the expansion, the coefficient of 𝑥 9 𝑦 3 (which corresponds to 𝑟 = 9) is
12 12−9 = −29 × 33 × 12!
( ) 2 9(−3 ) 9! ∙3!
9
12×11×10
= −29 × 33 ×
6

= −(210 × 33 × 11 × 10)
10
(ii). 𝑥3(1 − 2𝑥)10 = ∑10 𝑟 10−𝑟
𝑟=0 ( ) (−2𝑥) 1
𝑟
10
𝑥3(1 − 2𝑥)10 = ∑10 𝑟 𝑥𝑟+3
𝑟=0 ( 𝑟 ) (−2)

In the expansion, the coefficient of 𝑥12 (which corresponds to 𝑟 = 9) is

 10
( ) (−2 )9 = −(10 × 29) = −5120
9
2 15
(iii). (3𝑥2 − ) = ∑15 (15 2 𝑟 2 15−𝑟
𝑟=0 ) (3𝑥 ) (− )
𝑥 𝑥
𝑟
= ∑15 15 𝑟( )15−𝑟 3𝑟−15
𝑟=0 ( ) 3 −2 𝑥
𝑟
In the expansion, the coefficient of 𝑥 9 𝑦 3 (which corresponds to 𝑟 = 5) is
15 15−5 = (−2)10 × 35 × 15!
( ) 3 5(−2 ) 5! ∙10!
5
= 210 × 35 × 3003

2. Determine the coefficient of

(i) 𝑥𝑦𝑧2 in the expansion of (2𝑥 − 𝑦 − 𝑧)4

(ii) 𝑥11𝑦4 in the expansion of (2𝑥3 − 3𝑥𝑦2 + 𝑧2)6

(iii) 𝑥 2 𝑦2𝑧 3 in the expansion of (3𝑥 − 2𝑦 − 4𝑧)7

(iv) 𝑎2𝑏 3𝑐2𝑑5 in the expansion of (𝑎 + 2𝑏 − 3𝑐 + 2𝑑 + 5)16

(v) 𝑤 3𝑥 2 𝑦𝑧 2 in the expansion of (2𝑤 − 𝑥 + 3𝑦 − 2𝑧)8

Solution:

By the multinomial theorem, we have (𝑥1 + 𝑥2 + 𝑥3 + ⋯ ⋯ ⋯ + 𝑥𝑘 )𝑛 is 𝑛!

𝑛1! 𝑛2! 𝑛3!……𝑛 𝑘!

4
(i). The general term is the expansion of (2𝑥 − 𝑦 − 𝑧)4 is ( ) (2𝑥)𝑛1(−𝑦)𝑛2 (−𝑧)𝑛3
𝑛1 , 𝑛2 , 𝑛3

For 𝑛1 = 1, 𝑛2 = 1, 𝑛 3 = 2 this becomes

4 4
( ) (2𝑥)1(−𝑦)1(−𝑧)2=( ) (2)(−1)(−1)2𝑥𝑦𝑧2
1, 1, 2 1, 1, 2
4 4!
This shows that the required coefficient is ( ) (2)(−1)(−1)2 = × (−2) = −12
1, 1, 2 1! 1! 2!

6
(ii). The general term is the expansion of (2𝑥3 − 3𝑥𝑦2 + 𝑧2)6 is ( ) (2𝑥3)𝑛1 (−3𝑥𝑦2)𝑛2 (𝑧2)𝑛3
𝑛1 , 𝑛2 , 𝑛3

For 𝑛3 = 0, 𝑛2 = 2, 𝑛 1 = 3 this becomes

6 6
( ) (2𝑥3)3(−3𝑥𝑦2)2(𝑧2)0 = ( ) (2)3(−3)2(1)0𝑥11𝑦4
3, 2, 0 3, 2, 0
6 6!
This shows that the required coefficient is ( ) (2)3(3)2 = × 72 = 4320
3, 2, 0 3! 2!

7
(iii). The general term is the expansion of (3𝑥 − 2𝑦 − 4𝑧) 7 is ( ) (3𝑥)𝑛1(−2𝑦)𝑛2(−4𝑧)𝑛3
𝑛1 , 𝑛2 , 𝑛3
For 𝑛1 = 2, 𝑛2 = 2, 𝑛 3 = 3 this becomes

7 7
( ) (3𝑥)2(−2𝑦)2(−4𝑧)3=( ) (3) 2(−2)2(−4)3𝑥2𝑦2𝑧 3
2, 2, 3 2, 2, 3
This shows that the required coefficient is

7 ) (3)2(−2)2(−4)3 =
7!
( × 9 × 4 × (−64) = −483840
2, 2, 3 2! 2! 3!

(iv). The general term is the expansion of (𝑎 + 2𝑏 − 3𝑐 + 2𝑑 + 5)16 is

16
( (𝑎)𝑛1(2𝑏)𝑛2(−3𝑐)𝑛3(2𝑑)𝑛4(5)𝑛5
𝑛1, 𝑛2, 𝑛3, 𝑛4, 𝑛5 )

For 𝑛1 = 2, 𝑛 2 = 3, 𝑛3 = 2, 𝑛 4 = 5, 𝑛5 = 16 − (2 + 3 + 2 + 5) = 4, this becomes

16 16
( ) (𝑎)2(2𝑏)3(−3𝑐)2(2𝑑) 5(5)4 = ( ) (2)3(−3)2(2)5(5)4𝑎2𝑏3𝑐2𝑑5
2, 3, 2, 5, 4 2, 3, 2, 5, 4

This shows that the required coefficient is

16 ) (2)3(−3)2(2)5(5)4 =
16!
× 28 × 32 × 54 =
16!
( × 25 × 3 × 53
2, 3, 2, 5, 4 2! 3! 2! 5! 4! (4!)2

(v). The general term is the expansion of (2𝑤 − 𝑥 + 3𝑦 − 2𝑧)8 is

8 𝑛1 𝑛2 𝑛3 𝑛4
(
𝑛1, 𝑛 , 𝑛3 , 𝑛42 ) (2𝑤) (−𝑥) (3𝑦) (−2𝑧)

For 𝑛1 = 3, 𝑛2 = 2, 𝑛3 = 1, 𝑛4 = 2 this becomes

8 8
( ) (2𝑤)3(−𝑥)2(3𝑦)1(−2𝑧)2 = ( ) (2)3(−1)2(3)1(−2) 2) 𝑤 3𝑥 2 𝑦𝑧 2
3, 2, 1, 2 3, 2, 1, 2
This shows that the required coefficient is

8 ) (2)3(−1)2(3)1(−2)2) =
8!
( × 23 × 3 × 22 = 161280
3, 2, 1, 2 3! 2! 1! 2!
☻Combinations with repetitions:

Suppose we wish to select, with repetition, a combination of r objects from a set of n distinct objects. The
(𝑛+𝑟−1)!
number of such selections is given by 𝐶(𝑛 + 𝑟 − 1, 𝑟) ≡ ≡ 𝐶(𝑟 + 𝑛 − 1, 𝑛 − 1).
𝑟! (𝑛−1)!

In other words, 𝐶(𝑛 + 𝑟 − 1, 𝑟) ≡ 𝐶(𝑟 + 𝑛 − 1, 𝑛 − 1) represents the number of combinations of m distinct

objects, taken r at a time, with repetition allowed.

The following are other interpretations of this number:

𝐶(𝑛 + 𝑟 − 1, 𝑟) ≡ 𝐶(𝑟 + 𝑛 − 1, 𝑛 − 1) represents the number of ways in which r identical objects can be
distributed among 𝑛 distinct containers.

𝐶(𝑛 + 𝑟 − 1, 𝑟) ≡ 𝐶(𝑟 + 𝑛 − 1, 𝑛 − 1) represents the number of nonnegative integer solutions of the

equation.

Problems:

1. In how many ways we can distribute 10 identical marbles among 6 distinct containers?

Solution:

The selection consists in choosing with repetitions 𝑟 = 10 marbles for 𝑛 = 6 distinct containers
15!
The required number is 𝐶(6 + 10 − 1, 10) = 𝐶(15, 10) = = 3003
10! 5!

2. Find the number of non-negative integer solutions of the inequality 𝑥 1 + 𝑥 2 + 𝑥3 + ⋯ + 𝑥6 < 10

Solution:

We have to find the number of nonnegative integer solutions of the equation

𝑥 1 + 𝑥2 + 𝑥3 + ⋯ + 𝑥6 = 9 − 𝑥7

where 9 − 𝑥7 ≤ 9 so that 𝑥7 is non negative integer. Thus, the required number in the number of nonnegative
solutions of the equation.

x1 + x2 + x3 + ……+ x7 = 9
15!
This number is 𝐶(7 + 9 − 1, 9) = 𝐶(15, 9) = = 5005
9! 6!

3. In How many ways can we distribute 7 apples and 6 oranges among 4 children so that each child gets
at least 1 apple?

Solution:

Suppose we first give 1 apple to each child. This exhausts 4 apples. The remaining 3 apples can be distributed
among 4 children in 𝐶(4 + 3 − 1, 3) = 𝐶(6, 3) ways. Also, 6 oranges can be distributed among the 4
children in 𝐶(4 + 6 − 1, 6) = 𝐶(9, 6) ways. Therefore, by the product rule, the number ways of distributing
the given fruits under the given condition is
 6! 9!
𝐶(6, 3) × 𝐶(9, 6) = × = 20 × 84 = 1680
3! 3! 6! 3!

4. A message is made up of 12 different symbols and it is to be transmitted through a communication

channel. In addition to the 12 symbols, the transmitter will also send a total of 45 blank spaces
between the symbols, with at least three spaces between each pair of consecutive symbols. In how
many ways can the transmitter send such a message?

Solution:

The 12 symbols can be arranged in 12! Ways. For each of these arrangements, there are 11 positions between
the 12 symbols. Since there must be at least three spaces between successive symbols, 33 of the 45 spaces
will be used up. The remaining 12 spaces are to be accommodated in 11 positions. This can be done in
𝐶(11 + 12 − 1, 12) = 𝐶(22, 12) ways. Consequently, by the product rule, the required number is
22!
12! × 𝐶(22, 12) = 12! × = 3.097445 × 1014
12! × 10!
5. In how many ways can one distribute eight identical balls into four distinct containers so that (i) no
container is left empty? (ii) the fourth container gets an odd number of balls?

Solution:

(i). First, we distribute one ball in to each container. Then we distribute the remaining 4 balls into 4
containers. The number of ways of doing this is the required number. This number is

7!
𝐶(4 + 4 − 1, 4) = 𝐶(7, 4) = = 35
4! × 3!
(ii). If the fourth container has o get an odd number of balls, we have to put 1 or 3 or 5 or 7 balls into it.

Suppose we put 1 ball into the fourth container and the remaining 7 balls can be put into the remaining three
containers in

𝐶(3 + 7 − 1, 7) = 𝐶(9, 7) ways

Similarly, we put 3 balls into the fourth container and the remaining 5 balls can be put into the remaining
three containers in

𝐶(3 + 5 − 1, 5) = 𝐶(7, 5) ways

Similarly, we put 5 balls into the fourth container and the remaining 3 balls can be put into the remaining
three containers in

𝐶(3 + 3 − 1, 3) = 𝐶(5, 3) ways

Similarly, we put 7 balls into the fourth container and the remaining 1 ball can be put into the remaining
three containers in

𝐶(3 + 1 − 1, 1) = 𝐶(3, 1) ways

Thus, the total number of ways of distributing the given balls so that the fourth container gets an odd number
of balls is
 9! 7! 5! 3!
𝐶(9, 7) + 𝐶(7, 5) + 𝐶(5, 3) + 𝐶(3, 1) = + + + = 36 + 21 + 10 + 3 = 70
7!×2! 5!×2! 3!×2! 1!×2!

6. Find the number of integer solutions of 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 32 where 𝑥𝑖 ≥ 0, 1 ≤ 𝑖 ≤ 4.

Solution:

Given 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 = 32, where 𝑥𝑖 ≥ 0, 1 ≤ 𝑖 ≤ 4.

35!
The required number is 𝐶(4 + 32 − 1, 32) = 𝐶(35, 32) = = 6545
32!×3!

7. Find the number of positive integer solutions of the equation 𝑥1 + 𝑥2 + 𝑥3 = 17

Solution:

Given 𝑥1 + 𝑥2 + 𝑥3 = 17, we require 𝑥𝑖 ≥ 1, 1 ≤ 𝑖 ≤ 3.

Let us set 𝑦1 = 𝑥1 − 1, 𝑦2 = 𝑥2 − 1, 𝑦3 = 𝑥3 − 1, then 𝑦1, 𝑦2, 𝑦3 are all nonnegative integers.

Then the given equation is reads (𝑦1 + 1) + (𝑦2 + 1) + (𝑦3 + 1) = 17 or 𝑦1 + 𝑦2 + 𝑦3 = 14

16!
The required number is 𝐶(3 + 14 − 1, 14) = 𝐶(16, 14) = = 120
14!×2!

8. Find the number of positive integer solutions of the equation 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 30 where

𝑥1 ≥ 2, 𝑥2 ≥ 3, 𝑥3 ≥ 4, 𝑥4 ≥ 2, 𝑥5 ≥ 0

Solution:

Given 𝑥 1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 30

Let us set 𝑦1 = 𝑥1 − 2, 𝑦2 = 𝑥2 − 3, 𝑦3 = 𝑥3 − 4, 𝑦4 = 𝑥4 − 2, 𝑦5 = 𝑥5 then 𝑦1, 𝑦2, 𝑦3, 𝑦4, 𝑦5 are all

nonnegative integers.

Then the given equation is reads

(𝑦1 + 2) + (𝑦2 + 3) + (𝑦3 + 4) + (𝑦4 + 2) + (𝑦5 + 0) = 30 or 𝑦1 + 𝑦2 + 𝑦3 + 𝑦4 + 𝑦5 = 19

23!
The required number is 𝐶(5 + 19 − 1, 19) = 𝐶(23, 19) = = 8855
19!×4!