Recurrence Relation

Posted By on April 29, 2016


Download PDF
Mathematical Induction
Regular Expressions

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. We study the theory of linear recurrence relations and their solutions. Finally, we introduce generating functions for solving recurrence relations.

Definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing Fn as some combination of Fi with i<n).

Example − Fibonacci series: Fn = Fn−1 + Fn−2, Tower of Hanoi: Fn = 2Fn−1 + 1

Linear Recurrence Relations

A linear recurrence equation of degree k is a recurrence equation which is in the format xn = A1 xn−1 + A2 xn−1 + A3 xn−1 +… Ak xn−k (An is a constant and Ak ≠ 0) on a sequence of numbers as a first-degree polynomial.

These are some examples of linear recurrence equations −

Recurrence relations Initial values Solutions
Fn = Fn−1 + Fn−2 a1 = a2 = 1 Fibonacci number
Fn = Fn−1 + Fn−2 a1 = 1, a2 = 3 Lucas number
Fn = Fn−2 + Fn−3 a1 = a2 = a3 = 1 Padovan sequence
Fn = 2Fn−1 + Fn−2 a1 = 0, a2 = 1 Pell number

How to solve linear recurrence relation

Suppose, a two ordered linear recurrence relation is: Fn = AFn−1 + BFn−2 where A and B are real numbers.

The characteristic equation for the above recurrence relation is −

x2 − Ax − B = 0

Three cases may occur while finding the roots −

Case 1 − If this equation factors as (x − x1)(x − x1) = 0 and it produces two distinct real roots x1 and x2, then Fn = ax1n+ bx2n is the solution. [Here, a and b are constants]

Case 2 − If this equation factors as (x − x1)2 = 0 and it produces single real root x1, then Fn = a x1n + bn x1n is the solution.

Case 3 − If the equation produces two distinct real roots x1 and x2 in polar form x1 = r ∠ θ and x2 = r ∠(− θ), then Fn = rn (a cos(nθ) + b sin(nθ)) is the solution.

Problem 1

Solve the recurrence relation Fn = 5Fn−1 − 6Fn−2 where F0 = 1 and F1 = 4

Solution

The characteristic equation of the recurrence relation is −

x2 − 5x + 6 = 0,

So, (x − 3) (x − 2) = 0

Hence, the roots are −

x1 = 3 and x2 = 2

The roots are real and distinct. So, this is in the form of case 1

Hence, the solution is −

Fn = ax1n + bx2n

Here, Fn = a3n + b2n (As x1 = 3 and x2 = 2)

Therefore,

1 = F0 = a30 + b20 = a+b

4 = F1 = a31 + b21 = 3a+2b

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

Hence, the final solution is −

Fn = 2.3n + (−1) . 2n = 2.3n − 2n

Problem 2

Solve the recurrence relation Fn = 10Fn−1 − 25Fn−2 where F0 = 3 and F1 = 17

Solution

The characteristic equation of the recurrence relation is −

x2 − 10x −25 = 0,

So, (x − 5)2 = 0

Hence, there is single real root x1 = 5

As there is single real valued root, this is in the form of case 2

Hence, the solution is −

Fn = ax1n + bnx1n

3 = F0 = a.50 + b.0.50 = a

17 = F1 = a.51 + b.1.51 = 5a+5b

Solving these two equations, we get a = 3 and b = 2/5

Hence, the final solution is −

Fn = 3.5n + (2/5) .n.2n

Problem 3

Solve the recurrence relation Fn = 2Fn−1 − 2Fn−2 where F0 = 1 and F1 = 3

Solution

The characteristic equation of the recurrence relation is −

x2 −2x −2 = 0

Hence, the roots are −

x1 = 1 + i andx2 = 1 − i

In polar form,

x1 = r ∠ θ andx2 = r ∠(− θ), where r = √2 and θ = π / 4

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

Hence, the solution is −

Fn = (√2 )n (a cos(n. π / 4) + b sin(n. π / 4))

1 = F0 = (√2 )0 (a cos(0. π / 4) + b sin(0. π / 4) ) = a

3 = F1 = (√2 )1 (a cos(1. π / 4) + b sin(1. π / 4) ) = √2 ( a/√2 + b/√2)

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

Hence, the final solution is −

Fn = (√2 )n (cos(n. π / 4) + 2 sin(n. π / 4))

Particular Solutions

A recurrence relation is called non-homogeneous if it is in the form

Fn = AFn−1 + BFn−2 + F(n)where F(n) ≠ 0

The solution (an) of a non-homogeneous recurrence relation has two parts. First part is the solution (ah) of the associated homogeneous recurrence relation and the second part is the particular solution (at). So, an = ah + at.

Let F(n) = cxn and x1 and x2 are the roots of the characteristic equation −

x2 = Ax + B which is the characteristic equation of the associated homogeneous recurrence relation −

  • If x ≠ x1 and x ≠ x2, then at = Axn
  • If x = x1, x ≠ x2, then at = Anxn
  • If x = x1 = x2, then at = An2xn

Problem

Solve the recurrence relation Fn = 3Fn−1 + 10Fn−2 + 7.5n where F0 = 4 and F1 = 3

Solution

The characteristic equation is −

x2 − 3x −10 = 0

Or, (x − 5)(x + 2) = 0

Or, x1= 5 and x2 = −2

Since, x = x1 and x ≠ x2, the solution is −

at = Anxn = An5n

After putting the solution into the non-homogeneous relation, we get −

An5n = 3A(n − 1)5n−1 + 10A(n − 2)5n−2 + 7.5n

Dividing both sides by 5n−2, we get −

An52 = 3A(n − 1)5 + 10A(n − 2)50 + 7.52

Or, 25An = 15An − 15A + 10An − 20A + 175

Or, 35A = 175

Or, A = 5

So, Fn = n5n+1

Hence, the solution is −

Fn = n5n+1 + 6.(−2)n −2.5n

Generating Functions

Generating Functions represents sequences where each term of a sequence is expressed as a coefficient of a variable x in a formal power series.

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

Gx=a0+a1x+a2x2+.........+akxk+.........=k=0akxkGx=a0+a1x+a2x2+………+akxk+………=∑k=0∞akxk

Some Areas of Application

Generating functions can be used for the following purposes −

  • For solving a variety of counting problems. For example, the number of ways to make change for a Rs. 100 note with the notes of denominations Rs.1, Rs.2, Rs.5, Rs.10, Rs.20 and Rs.50
  • For solving recurrence relations
  • For proving some of the combinatorial identities
  • For finding asymptotic formulae for terms of sequences

Problem 1

What are the generating functions for the sequences {ak} with ak= 2 and = 3k?

Solution

When ak = 2, generating function,

G(x)=k=02xk=2+2x+2x2+2x3+.........G(x)=∑k=0∞2xk=2+2x+2×2+2×3+………

When ak=3k,G(x)=k=03kxk=0+3x+6x2+9x3+......ak=3k,G(x)=∑k=0∞3kxk=0+3x+6×2+9×3+……

Problem 2

What is the generating function of the infinite series; 1, 1, 1, 1, ……….?

Solution

Here, ak = 1, for 0 ≤k≤ ∞.

Hence, G(x)=1+x+x2+x3+........=1(1x)G(x)=1+x+x2+x3+……..=1(1−x)

Some Useful Generating Functions

  • For ak=ak,G(x)=k=0akxk=1+ax+a2x2+.........=1(1ax)ak=ak,G(x)=∑k=0∞akxk=1+ax+a2x2+………=1(1−ax)
  • For ak=(k+1),G(x)=k=0(k+1)xk=1+2x+3x2.........=1(1x)2ak=(k+1),G(x)=∑k=0∞(k+1)xk=1+2x+3×2………=1(1−x)2
  • For ak=cnk,G(x)=k=0cnkxk=1+cn1x+cn2x2+.........+x2=(1+x)nak=ckn,G(x)=∑k=0∞cknxk=1+c1nx+c2nx2+………+x2=(1+x)n
  • For ak=1k!,G(x)=k=0xkk!=1+x+x22!+x33!.........=exak=1k!,G(x)=∑k=0∞xkk!=1+x+x22!+x33!………=ex
Mathematical Induction
Regular Expressions

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com