Discrete Mathematics - Recurrence Relation

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 pnear 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 $F_n$ as some combination of $F_i$ with $i < n$).

Example − Fibonacci series − $F_n = F_{n-1} + F_{n-2}$, Tower of Hanoi − $F_n = 2F_{n-1} + 1$

Linear Recurrence Relations

A pnear recurrence equation of degree k or order k is a recurrence equation which is in the format $x_n= A_1 x_{n-1}+ A_2 x_{n-1}+ A_3 x_{n-1}+ dots A_k x_{n-k} $($A_n$ is a constant and $A_k eq 0$) on a sequence of numbers as a first-degree polynomial.

These are some examples of pnear recurrence equations −

How to solve pnear recurrence relation

Suppose, a two ordered pnear recurrence relation is − $F_n = AF_{n-1} +BF_{n-2}$ where A and B are real numbers.

The characteristic equation for the above recurrence relation is −

$$x^2 - Ax - B = 0$$

Three cases may occur while finding the roots −

Case 1 − If this equation factors as $(x- x_1)(x- x_1) = 0$ and it produces two distinct real roots $x_1$ and $x_2$, then $F_n = ax_1^n+ bx_2^n$ is the solution. [Here, a and b are constants]

Case 2 − If this equation factors as $(x- x_1)^2 = 0$ and it produces single real root $x_1$, then $F_n = a x_1^n+ bn x_1^n$ is the solution.

Case 3 − If the equation produces two distinct complex roots, $x_1$ and $x_2$ in polar form $x_1 = r angle heta$ and $x_2 = r angle(- heta)$, then $F_n = r^n (a cos(n heta)+ b sin(n heta))$ is the solution.

Problem 1

Solve the recurrence relation $F_n = 5F_{n-1} - 6F_{n-2}$ where $F_0 = 1$ and $F_1 = 4$

Solution

The characteristic equation of the recurrence relation is −

$$x^2 - 5x + 6 = 0,$$

So, $(x - 3) (x - 2) = 0$

Hence, the roots are −

$x_1 = 3$ and $x_2 = 2$

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

Hence, the solution is −

$$F_n = ax_1^n + bx_2^n$$

Here, $F_n = a3^n + b2^n (As x_1 = 3 and x_2 = 2)$

Therefore,

$1 = F_0 = a3^0 + b2^0 = a+b$

$4 = F_1 = a3^1 + b2^1 = 3a+2b$

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

Hence, the final solution is −

$$F_n = 2.3^n + (-1) . 2^n = 2.3^n - 2^n $$

Problem 2

Solve the recurrence relation − $F_n = 10F_{n-1} - 25F_{n-2}$ where $F_0 = 3$ and $F_1 = 17$

Solution

The characteristic equation of the recurrence relation is −

$$ x^2 - 10x -25 = 0$$

So $(x - 5)^2 = 0$

Hence, there is single real root $x_1 = 5$

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

Hence, the solution is −

$F_n = ax_1^n + bnx_1^n$

$3 = F_0 = a.5^0 + (b)(0.5)^0 = a$

$17 = F_1 = a.5^1 + b.1.5^1 = 5a+5b$

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

Hence, the final solution is − $F_n = 3.5^n +( 2/5) .n.2^n $

Problem 3

Solve the recurrence relation $F_n = 2F_{n-1} - 2F_{n-2}$ where $F_0 = 1$ and $F_1 = 3$

Solution

The characteristic equation of the recurrence relation is −

$$x^2 -2x -2 = 0$$

Hence, the roots are −

$x_1 = 1 + i$ and $x_2 = 1 - i$

In polar form,

$x_1 = r angle heta$ and $x_2 = r angle(- heta),$ where $r = sqrt 2$ and $ heta = frac{pi}{4}$

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

Hence, the solution is −

$F_n = (sqrt 2 )^n (a cos(n .sqcap /4) + b sin(n .sqcap /4))$

$1 = F_0 = (sqrt 2 )^0 (a cos(0 .sqcap /4) + b sin(0 .sqcap /4) ) = a$

$3 = F_1 = (sqrt 2 )^1 (a cos(1 .sqcap /4) + b sin(1 . sqcap /4) ) = sqrt 2 ( a/ sqrt 2 + b/ sqrt 2)$

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

Hence, the final solution is −

$F_n = (sqrt 2 )^n (cos(n .pi /4 ) + 2 sin(n .pi /4 ))$

Non-Homogeneous Recurrence Relation and Particular Solutions

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

$F_n = AF_{n-1} + BF_{n-2} + f(n)$ where $f(n) e 0$

Its associated homogeneous recurrence relation is $F_n = AF_{n–1} + BF_{n-2}$

The solution $(a_n)$ of a non-homogeneous recurrence relation has two parts.

First part is the solution $(a_h)$ of the associated homogeneous recurrence relation and the second part is the particular solution $(a_t)$.

$$a_n=a_h+a_t$$

Solution to the first part is done using the procedures discussed in the previous section.

To find the particular solution, we find an appropriate trial solution.

Let $f(n) = cx^n$ ; let $x^2 = Ax + B$ be the characteristic equation of the associated homogeneous recurrence relation and let $x_1$ and $x_2$ be its roots.

If $x e x_1$ and $x e x_2$, then $a_t = Ax^n$

If $x = x_1$, $x e x_2$, then $a_t = Anx^n$

If $x = x_1 = x_2$, then $a_t = An^2x^n$

Example

Let a non-homogeneous recurrence relation be $F_n = AF_{n–1} + BF_{n-2} + f(n)$ with characteristic roots $x_1 = 2$ and $x_2 = 5$. Trial solutions for different possible values of $f(n)$ are as follows −

Problem

Solve the recurrence relation $F_n = 3F_{n-1} + 10F_{n-2} + 7.5^n$ where $F_0 = 4$ and $F_1 = 3$

Solution

This is a pnear non-homogeneous relation, where the associated homogeneous equation is $F_n=3F_{n-1}+10F_{n-2}$ and $f(n)=7.5^n$

The characteristic equation of its associated homogeneous relation is −

$$x^2 - 3x -10 = 0$$

Or, $(x - 5)(x + 2) = 0$

Or, $x_1= 5$ and $x_2 = -2$

Hence $a_h = a.5^n + b.(-2)^n$ , where a and b are constants.

Since $f(n) = 7.5^n$, i.e. of the form $c.x^n$, a reasonable trial solution of at will be $Anx^n$

$a_t = Anx^n = An5^n$

After putting the solution in the recurrence relation, we get −

$An5^n = 3A(n – 1)5^{n-1} + 10A(n – 2)5^{n-2} + 7.5^n$

Dividing both sides by $5^{n-2}$, we get

$An5^2 = 3A(n - 1)5 + 10A(n - 2)5^0 + 7.5^2$

Or, $25An = 15An - 15A + 10An - 20A + 175$

Or, $35A = 175$

Or, $A = 5$

So, $F_n = An5^n= 5n5^n=n5^{n+1}$

The solution of the recurrence relation can be written as −

$F_n = a_h + a_t$

$=a.5^n+b.(-2)^n+n5^{n+1}$

Putting values of $F_0 = 4$ and $F_1 = 3$, in the above equation, we get $a = -2$ and $b = 6$

Hence, the solution is −

$F_n = n5^{n+1} + 6.(-2)^n -2.5^n$

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 $a_0, a_1, a_2,dots, a_k,dots,$ the generating function will be −

$$G_x=a_0+a_1x+a_2x^2+ dots +a_kx^k+ dots = sum_{k=0}^{infty}a_kx^k$$

Some Areas of Apppcation

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 $lbrace {a_k} brace$ with $a_k = 2$ and $a_k = 3k$?

Solution

When $a_k = 2$, generating function, $G(x) = sum_{k = 0}^{infty }2x^{k} = 2 + 2x + 2x^{2} + 2x^{3} + dots$

When $a_{k} = 3k, G(x) = sum_{k = 0}^{infty }3kx^{k} = 0 + 3x + 6x^{2} + 9x^{3} + dotsdots$

Problem 2

What is the generating function of the infinite series; $1, 1, 1, 1, dots$?

Solution

Here, $a_k = 1$, for $0 le k le infty$

Hence, $G(x) = 1 + x + x^{2} + x^{3}+ dots dots= frac{1}{(1 - x)}$

Some Useful Generating Functions

For $a_k = a^{k}, G(x) = sum_{k = 0}^{infty }a^{k}x^{k} = 1 + ax + a^{2}x^{2} +dots dots dots = 1/ (1 - ax)$

For $a_{k} = (k + 1), G(x) = sum_{k = 0}^{infty }(k + 1)x^{k} = 1 + 2x + 3x^{2} dots dots dots =frac{1}{(1 - x)^{2}}$

For $a_{k} = c_{k}^{n}, G(x) = sum_{k = 0}^{infty} c_{k}^{n}x^{k} = 1+c_{1}^{n}x + c_{2}^{n}x^{2} + dots dots dots + x^{2} = (1 + x)^{n}$

For $a_{k} = frac{1}{k!}, G(x) = sum_{k = 0}^{infty }frac{x^{k}}{k!} = 1 + x + frac{x^{2}}{2!} + frac{x^{3}}{3!}dots dots dots = e^{x}$