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 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 $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 linear 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 \neq 0$) on a sequence of numbers as a first-degree polynomial.

These are some examples of linear recurrence equations −

How to solve linear recurrence relation

Suppose, a two ordered linear 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 \theta$ and $x_2 = r \angle(- \theta)$, then $F_n = r^n (a cos(n\theta)+ b sin(n\theta))$ 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 \theta$ and $x_2 = r \angle(- \theta),$ where $r = \sqrt 2$ and $\theta = \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) \ne 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 \ne x_1$ and $x \ne x_2$, then $a_t = Ax^n$

• If $x = x_1$, $x \ne 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 linear 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 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 $\lbrace {a_k} \rbrace$ 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} + \dots\dots$

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}$