Discrete Mathematics

1

Module-4

Recurrence Relations

����In this chapter, we will discuss how recursive techniques can derive sequences and be used for�solving counting problems. ���The procedure for finding the terms of a sequence in a recursive manner is called recurrence relation.���

2

�The sequence which is defined by indicating a relation connecting its general term an with an-1, an-2, etc is called a recurrence relation for the sequence.���A recurrence relation is an equation that defines a sequence based on a rule that gives the next term as a function of the previous term(s). ��The simplest form of a recurrence relation is the case where the next term depends only on the immediately previous term.���

3

4

If we denote the nth term in the sequence by xn, such a recurrence relation is of the form

for some function f.

​

One such example is xn+1=2−xn/2.

​

A recurrence relation can also be higher order, where the term xn+1 could depend not only on the previous term xn

but also on earlier terms such as xn−1, xn−2, etc.

​

​

​

​

​

Recurrence relation is also called as "Linear recursive sequences".

5

Common examples of Recurrence Relations are

Example

Let {a_n} be a sequence that satisfies the recurrence relation a_n=a_n-1 – a_n-2 for n=2, 3, 4, … and suppose that a₀=3 and a₁=5, what are a₂ and a₃?

​

Using the recurrence relation,

a₂=a₁-a₀=5-3=2

and

a₃=a₂-a₁=2-5=-3

6

Example

Determine whether the sequence {a_n}, where a_n=3n for every nonnegative integer n, is a solution of the recurrence relation a_n=2a_n-1 – a_n-2 for n=2, 3, 4, …

​

Suppose a_n=3n for every nonnegative integer n. Then for n≥2, we have 2a_n-1-a_n-2=2(3(n-1))-3(n-2)=3n=a_n.

​

Thus, {a_n} where a_n=3n is a solution for the recurrence relation

7

8

Order of the Recurrence Relation:

​

The order of the recurrence relation or difference equation is defined to be the difference between the highest and lowest subscripts of f(x) or a_r=y_k.

​

Example1: The equation 13a_r+20a_r-1=0 is a first order recurrence relation.

​

​

Example2: The equation 8f (x) + 4f (x + 1) + 8f (x+2) = k (x)

​

​

9

Degree of the Difference Equation:

The degree of a difference equation is defined to be the highest power of f (x) or a_r=y_k

​

Example1: The equation y³_k+3+2y²_k+2+2y_k+1=0 has the degree 3, as the highest power of y_k is 3.

​

Example2: The equation a⁴_r+3a³_r-1+6a²_r-2+4a_r-3 =0 has the degree 4, as the highest power of a_r is 4.

​

Example3: The equation y_k+3 +2y_k+2 +4y_k+1+2y_k= k(x) has the degree 1, because the highest power of y_k is 1 and its order is 3.

Example4: The equation f (x+2h) - 4f(x+h) +2f(x) = 0 has the degree1 and its order is 2.

A Recurrence Relations is called linear if its degree is one.

​

The general form of linear recurrence relation with constant coefficient is

​

​

​

Where C0,C1,C2......Cn are constant and R(n) is same function of independent variable n.

​

A solution of a recurrence relation in any function which satisfies the given equation.

Linear Homogeneous Recurrence Relations with Constant Coefficients:

​

The equation is said to be linear homogeneous difference equation if and only if R (n) = 0 and it will be of order n.

​

The equation is said to be linear non-homogeneous difference equation if R (n) ≠ 0.

12

13

Solving Recurrence Relations

In general, we would prefer to have an explicit formula to compute the value of a_n rather than conducting n iterations.

​

For one class of recurrence relations, we can obtain such formulas in a systematic way.

​

Those are the recurrence relations that express the terms of a sequence as linear combinations of previous terms.

16

Solving Recurrence Relations

Definition: A linear homogeneous recurrence relation of degree k with constant coefficients is a recurrence relation of the form:

a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k,

​

Where c₁, c₂, …, c_k are real numbers, and c_k ≠ 0.

​

​

A sequence satisfying such a recurrence relation is uniquely determined by the recurrence relation and the k initial conditions

​

a₀ = C₀, a₁ = C₁, a₂ = C₂, …, a_k-1 = C_k-1.

17

Solving Recurrence Relations

Basically, when solving such recurrence relations, we try to find solutions of the form a_n = rⁿ, where r is a constant.

​

a_n = rⁿ is a solution of the recurrence relation� a_n = c₁a_n-1 + c₂a_n-2 + … + c_ka_n-k

​

if and only if rⁿ = c₁r^n-1 + c₂r^n-2 + … + c_kr^n-k.

​

Divide this equation by r^n-k and subtract the right-hand side from the left:

r^k - c₁r^k-1 - c₂r^k-2 - … - c_k-1r - c_k = 0

​

This is called the characteristic equation of the recurrence relation.

18

Solving Recurrence Relations

The solutions of this equation are called the characteristic roots of the recurrence relation.

​

​

Let us consider linear homogeneous recurrence relations of degree two.

​

​

Theorem 1: Let c₁ and c₂ be real numbers. Suppose that

r² – c₁r – c₂ = 0 has two distinct roots r₁ and r₂.

​

Then the sequence {a_n} is a solution of the recurrence relation

​

a_n = c₁a_n-1 + c₂a_n-2 if and only if

a_n = α₁r₁ⁿ + α₂r₂ⁿ for n = 0, 1, 2, …,

where α₁ and α₂ are constants.

​

19

Solving Recurrence Relations

Example: What is the solution of the recurrence relation

a_n = a_n-1 + 2a_n-2 with a₀ = 2 and a₁ = 7 ?

​

Solution: The characteristic equation of the recurrence relation is r² – r – 2 = 0.

​

Its roots are r = 2 and r = -1.

​

Hence, the sequence {a_n} is a solution to the recurrence relation if and only if:

​

a_n = α₁2ⁿ + α₂(-1)ⁿ for some constants α₁ and α₂.

20

Solving Recurrence Relations

Given the equation a_n = α₁2ⁿ + α₂(-1)ⁿ and the initial conditions a₀ = 2 and a₁ = 7, it follows that

a₀ = 2 = α₁ + α₂

a₁ = 7 = α₁⋅2 + α₂ ⋅(-1)

​

Solving these two equations gives us�2=α1​+α2​(Equation 1)

7=2α1​−α2​(Equation 2)​

First, we can add Equation 1 and Equation 2 to eliminate α2​:

9=3α1 Therefore α1=3 & α2 = -1

​

These values satisfy both equations: For Equation 1: 2=3−1

For Equation 2: 7=2⋅3−(−1)=6+1

Therefore, α1​=3 and α2=−1 are the correct solutions.

21

Solving Recurrence Relations

​

Therefore, the solution to the recurrence relation and initial conditions is the sequence {a_n} with

​

a_n = 3⋅2ⁿ – (-1)ⁿ.

22

Solving Recurrence Relations

But what happens if the characteristic equation has only one root?

​

How can we then match our equation with the initial conditions a₀ and a₁ ?

​

Theorem 2: Let c₁ and c₂ be real numbers with c₂ ≠ 0. Suppose that r² – c₁r – c₂ = 0 has only one root r₀. �

A sequence {a_n} is a solution of the recurrence relation

a_n = c₁a_n-1 + c₂a_n-2 if and only if � a_n = α₁r₀ⁿ + α₂nr₀ⁿ, for n = 0, 1, 2, …,

where α₁ and α₂ are constants.

23

Solving Recurrence Relations

Example: What is the solution of the recurrence relation

a_n = 6a_n-1 – 9a_n-2 with a₀ = 1 and a₁ = 6?

​

Solution: The only root of r² – 6r + 9 = 0 is r₀ = 3.

�Hence, the solution to the recurrence relation is

a_n = α₁3ⁿ + α₂n3ⁿ for some constants α₁ and α₂.

​

To match the initial condition, we need

a₀ = 1 = α₁� a₁ = 6 = α₁⋅3 + α₂⋅3

Solving these equations yields α₁ = 1 and α₂ = 1.

Consequently, the overall solution is given by

a_n = 3ⁿ + n3ⁿ.

24

The closed-form solution is a n​ =Ar^ n , where A is the initial condition.

Solve the recurrence relation

Solution

​

The characteristic equation of the recurrence relation is − x2−5x+6=0,

Hence, the roots are − x1=3 and x2=2

Hence, there is single real root x1=5