Homogeneous Recurrence Relation In Discrete Mathematics Pdf

What is Recurrence Relation in Discrete Mathematics?

The manner in which the terms of a sequence are found in recursive manner is called recurrence relation.

Definition

An equation which defines a sequence recursively, where the next term is a function of the previous terms is known as recurrence relation.

A recurrence relation is an equation that recursively defines a sequence

What is Linear Recurrence Relations?

A linear recurrence equation of degree k or order k is a recurrence equation which is in the format (An is a constant and Ak≠0) on a sequence of numbers as a first-degree polynomial.

Some of the examples of linear recurrence equations are as follows:

Recurrence relations	Initial values	Solutions
		Fibonacci number
		Lucas Number
		Padovan sequence
		Pell number

How to solve linear recurrence relation?

For instance, the two ordered linear recurrence relation is -

where A and B are real numbers.

For the above recurrence relation, the characteristic equation is :

Problem 1

Solve the recurrence relation

Solution

For the recurrence relation, the characteristic equation is:

Solving these two equations, we get a=2 and b=−1

Hence, the final solution is −

Problem 2

Solution

For the recurrence relation, the characteristic equation is:

Problem 3

Solve the recurrence relation

Solution

For the recurrence relation, the characteristic equation is as follows:

The roots are imaginary. So, this is in the form of case 3.

Hence, the solution is −

Solving these two equations we get a=1 and b=2

Hence, the final solution is −

Non-Homogeneous Recurrence Relation and Particular Solutions

A non-homogeneous recurrence is in the form of:

The associated homogeneous recurrence relation will be

There are two parts of a solution of a non-homogeneous recurrence relation.

The first part of the solution is the solution of the associated homogeneous recurrence relation and the second part of the solution is the solution of that particular solution .

By finding an appropriate trial solution, the particular solution can be found.

For instance, the characteristic equation of the associated homogeneous recurrence relation be

Example

For the non-homogeneous recurrence relation

With the characteristic roots of

The trial solution is as follows:

Problem

Solution

For the linear non-homogeneous relation, the associated homogeneous equation is:

The characteristic equation of its associated homogeneous relation is −

Once the solution is put in the recurrence relation, the result obtained is:

The solution of the recurrence relation can be written as −

What is Generating Functions?

When each term of a sequence is expressed as a coefficient of the variable x in a power series, the sequence is represented as Generating functions.

Mathematically, for an infinite sequence, say a0,a1,a2,…,ak,…,a0,a1,a2,…,ak,…, the generating function will be −

Some Areas of Application of Generating Functions

Generating functions can be used for the following purposes −

A variety of counting problems are solved by using the Generating functions. For instance, number of ways in which a Rs. 100 note can be made with the denominations of Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50
Recurrent relations are solved
Some of the combinational identities are proved
For the terms of sequence, asymptotic formula is found.