RECURRENCE
RELATION
Definition:
• A recurrence relation is a mathematical equation
that defines a sequence where each term is
expressed in terms of one or more previous terms.
• It's a powerful tool for modeling problems where
the current state depends on previous states.
A recurrence relation has the general form:
• Recurrence equation: Expresses a term using previous
terms
• Initial conditions: Specifies the first few terms to start the
sequence
For example: an = 2an-1 + 1 with a1 = 1 defines a sequence
where each term is twice the previous term plus one.
Exercise :
Find first five terms of the sequence :
i. an = 3an-1 , a1 = 1.
ii. an = 5an-1 + 1 , a1 = 3.
iii. an = 4an-1 + 5an-2 , a1 = 2, a2 = 6
Recursive
and
Explicit
formula
Recursive Formula
A recursive formula defines each term using previous terms in
the sequence.
Characteristics:
Requires initial conditions to start the sequence
Each term depends on one or more previous terms
Examples:
• Arithmetic sequence: an = an-1 + d with a1 = a
• Geometric sequence: an = r × an-1 with a1 = a
• Fibonacci: Fn = Fn-1 + Fn-2 with F0 = 0, F1 = 1
• Tower of Hanoi: Tn = 2 Tn-1 + 1 with T1 = 1
Method 2: Characteristic Equation
This is the most powerful and systematic approach for solving linear
homogeneous recurrence relations with constant coefficients.
Consider second order equation:
Example 1
Solve the recurrence relation an = 5an−1 − 6an−2 where a0 = 1 and a1 = 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. Hence, the solution is: an = Ax1n + Bx2n
Here, an = A(3n ) + B(2n ) (As x1 = 3 and x2 = 2)
Therefore,
1 = a0 = A(30 ) + B (20 ) = A + B
4 = a1 = A(31 ) + b(21 ) = 3a + 2B
Solving these two equations, we get A = 2 and B = −1
Hence, the final solution is − an = 2.3n + (−1).2n = 2.3n − 2n
Example 3
Solve the recurrence relation : an = 10an−1 – 25an−2 where a0 = 3 and a1 = 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 : an = Ax1n + Bnx1n
Put n = 0, 3 = a0 = A.50 + B(0 x 5)0 = A
Put n = 1, 17 = a1= A.51 + B (1.51) = 5A + 5B
Solving these two equations, we get A = 3 and B = 2/5
Hence, the final solution is : an = 3.5n+(2/5).n.5n
Exercise :
1. Find the solution to the recurrence relation an = 3an−1 + 4an−2 with initial terms a0 = 2 and a1=3.
2. Solve the recurrence relation an = 2an−1 − an−2.
What is the solution if the initial terms are a0 = 1 and a1 = 2?
3. Solve the recurrence relation an= 3an−1 +10an−2 with initial terms a0= 4 and a1=1.
4. Consider the recurrence relation an= 4an−1 − 4an−2.
Find the general solution to the recurrence relation.
a. Find the solution when a0 =1 and a1 =2.
b. Find the solution when a0 =1 and a1 =8.
5. Find first four terms of following sequence. Also find its explicit formula.
i. an = n an - 1 , a1 = 2 ii. an = 5an-1 + 1, a1 = 3
iii. an = 2n an-1 , a1 = 5 iv. an = (-3.1)an-1 , a1 = 2
Fibonacci
Sequence
The Fibonacci sequence is one of the most famous and fascinating
mathematical sequences, appearing throughout mathematics,
nature, art, and science.
Recursive Definition
Fn = Fn-1 + Fn-2 with initial conditions: F0 = 0 and F1 = 1
The Sequence
First 20 terms: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
610, 987, 1597, 2584, 4181, ...
Why Fibonacci Numbers are Special
1. Mathematical Beauty: Simple recursive definition leads to complex,
beautiful properties
2. Natural Occurrence: Appears frequently in biological systems
3. Golden Ratio Connection: Links discrete mathematics to continuous
geometry
4. Computational Interest: Provides examples for algorithm analysis
5. Artistic Applications: Creates aesthetically pleasing proportions
6. Cross-Disciplinary: Connects pure mathematics to applied sciences
The Fibonacci sequence demonstrates how simple mathematical rules can
generate patterns that appear throughout the natural world, making it one
of the most studied and celebrated sequences in mathematics.
Tower of
Hanoi
The Tower of Hanoi is a classic mathematical puzzle that beautifully
demonstrates recursive thinking, exponential growth, and provides an excellent
example of recurrence relations in action.
The Puzzle
Setup
Three pegs: Usually labeled A, B, and C (or Source, Auxiliary, Destination)
n disks: Different sizes, initially stacked on peg A in decreasing order (largest at
bottom)
Goal: Move all disks to peg C
Rules
One disk at a time: You can only move one disk per move
Top disk only: You can only move the top disk from any peg
No large on small: A larger disk can never be placed on top of a smaller disk
Recursive approach
Consider 2 disks on peg A.
We need to move them to peg C
First, move disk 1 from peg A to peg C
Now that disk 2—the bottommost disk—is exposed, move it to peg B
Finally, move disk 1 from peg C to peg B
The Legend
Buddhist Monastery Legend
According to legend:
• In a temple in Hanoi, monks work continuously on a 64-disk Tower of Hanoi
• When they complete it, the world will end
• Time required: 2⁶⁴ - 1 = 18,446,744,073,709,551,615 moves
• If one move per second: About 585 billion years (much longer than the age of
the universe!)
Historical Note
The puzzle was actually invented by French mathematician Édouard Lucas in
1883, not ancient Buddhist monks. The legend was created as a marketing tool
for the puzzle.
