
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
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 −
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 − $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_{n1} + 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_{n1} + 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 −
f(n) | Trial solutions |
---|---|
4 | A |
5.2n | An2n |
8.5n | An5n |
4n | A4n |
2n2+3n+1 | An2+Bn+C |
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}$