Scribd
Upload
20 views25 pages

Discrete Math Recurrence Relations

The document contains lecture notes from a Discrete Mathematics course at BITS Pilani. It includes explanations and examples of recurrence relations, generating functions, and Pascal's triangle. Recurrence relations are explored for the number of arrangements of distinct objects in a row and the number of binary sequences of length n with no consecutive 0s. It also shows how to compute terms in a recurrence relation and construct Pascal's triangle.

Uploaded by

Yashwanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views25 pages

Discrete Math Recurrence Relations

The document contains lecture notes from a Discrete Mathematics course at BITS Pilani. It includes explanations and examples of recurrence relations, generating functions, and Pascal's triangle. Recurrence relations are explored for the number of arrangements of distinct objects in a row and the number of binary sequences of length n with no consecutive 0s. It also shows how to compute terms in a recurrence relation and construct Pascal's triangle.

Uploaded by

Yashwanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 25

BITS-Pilani

1st Semester 2022-23

MATH F213
BITS Pilani (Discrete Mathematics)
Pilani|Dubai|Goa|Hyderabad
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Check if the given recurrence relation is linear, homogeneous
and if linear, find its degree.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956


BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Find a recurrence relation for the number of ways to
arrange n distinct objects in a row.

Always start by assuming what is an.


Let an denote the number of arrangements of n distinct
objects.
There are n choices for the first object in the row. This
choice can be followed by any arrangement of the
remaining n −1 objects; that is, by the an−1 arrangements
of the remaining n −1 objects.
Thus an = nan−1.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956


Find a recurrence relation for the number of binary
sequences of length n with no consecutive 0’s.

an = an-1 + an-2 with initial conditions a0 = 1 (empty


sequence) and a1 = 2.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Write down the corresponding recurrence relation.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956


Compute D2, D3, D4

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956


BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Pascal’s triangle.
Each number in this table, except the first and last numbers in a
row, is the sum of the two neighboring numbers in the preceding
row.

BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956


BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956

You might also like