RECURRENCE
RELATIONS
Dr. Yogeshri Gaidhani
1
RECURRENCE RELATION
{1, 2, 4, 8, ?, ?,… }
a0=1, a1=2, a2=4,a3=8…, an=?
an=2n
{1, 1, 2, 3, 5, 8,… }
a0=1, a1=1, a2=2,…
2
RECURRENCE RELATIONS
A recurrence relation for the sequence {an}
is an equation that expresses an is terms of
one or more of the previous terms of the
sequence, namely, a0, a1, …, an-1, for all
integers n with n n0, where n0 is a
nonnegative integer.
a(n) = 2 * a(n-1) {3, 6, 12, 24,… }
{1, 1, 1, 1,…}
A sequence is called a solution of a
recurrence relation if it terms satisfy the
recurrence relation.
3
RECURRENCE RELATIONS
Inother words, a recurrence relation is like
a recursively defined sequence, but without
specifying any initial values (initial
conditions).
Therefore,the same recurrence relation can
have (and usually has) multiple solutions.
Ifboth the initial conditions and the
recurrence relation are specified, then the
sequence is uniquely determined.
4
RECURRENCE RELATIONS
Example:
Consider the recurrence relation
an = 2an-1 – an-2 for n = 2, 3, 4, …
Is the sequence {an} with an=3n a solution of
this recurrence relation?
For n 2 we see that
2an-1 – an-2 = 2(3(n – 1)) – 3(n – 2) = 3n = an.
Therefore, {an} with an=3n is a solution of the
recurrence relation.
5
RECURRENCE RELATIONS
Isthe sequence {an} with an=K, where K is a
constant, a solution of the same recurrence
relation?
For n 2 we see that
2an-1 – an-2 = 2K - K = K = an.
Therefore, {an} with an=K is also a solution
of the recurrence relation.
6
MODELING WITH RECURRENCE
RELATIONS
Example:
Someone deposits Rs.10,000 in a savings
account at a bank yielding 5% per year with
interest compounded annually. How much
money will be in the account after 30 years?
Solution:
Let P denote the amount in the account
n
after n years.
How can we determine P on the basis of P ?
n n-1
7
MODELING WITH RECURRENCE RELATIONS
We can derive the following recurrence relation:
P = P
n n-1 + 0.05Pn-1 = 1.05Pn-1.
The initial condition is P = 10,000.
0
Then we have:
P = 1.05P
1 0
P = 1.05P = (1.05)2P
2 1 0
P = 1.05P = (1.05)3P
3 2 0
…
P = 1.05P = (1.05)n
P0
n n-1
We now have a formula to calculate Pn for any
natural number n and can avoid the iteration.
8
MODELING WITH RECURRENCE RELATIONS
Let us use this formula to find P30 under the
initial condition P0 = 10,000:
P
30 = (1.05)3010,000 = 43,219.42
After 30 years, the account contains
Rs. 43,219.42.
9
MODELING WITH RECURRENCE RELATIONS
Example:
Let a denote the number of bit strings of
n
length n that do not have two consecutive 0s
(“valid strings”). Find a recurrence relation
and give initial conditions for the sequence
{an}.
Solution:
Idea: The number of valid strings equals the
number of valid strings ending with a 0 plus
the number of valid strings ending with a 1.
10
MODELING WITH RECURRENCE RELATIONS
Let us assume that n 3, so that the string
contains at least 3 bits.
Let us further assume that we know the
number an-1 of valid strings of length (n – 1).
Then how many valid strings of length n are
there, if the string ends with a 1?
There are a
n-1 such strings, namely the set of
valid strings of length (n – 1) with a 1
appended to them.
Note: Whenever we append a 1 to a valid
string, that string remains valid.
11
MODELING WITH RECURRENCE RELATIONS
Now we need to know: How many valid
strings of length n are there, if the string
ends with a 0?
Valid strings of length n ending with a 0 must
have a 1 as their (n – 1)th bit (otherwise they
would end with 00 and would not be valid).
And what is the number of valid strings of length
(n – 1) that end with a 1?
We already know that there are a
n-1 strings of
length n that end with a 1.
Therefore, there are a
n-2 strings of length (n – 1)
that end with a 1.
12
MODELING WITH RECURRENCE RELATIONS
So there are an-2 valid strings of length n that
end with a 0 (all valid strings of length (n– 2)
with 10 appended to them).
Aswe said before, the number of valid
strings is the number of valid strings ending
with a 0 plus the number of valid strings
ending with a 1.
That gives us the following recurrence
relation: an = an-1 + an-2
13
14
MODELING WITH RECURRENCE RELATIONS
What are the initial conditions?
a = 2 (0 and 1)
1
a = 3 (01, 10, and 11)
2
a = a2 + a1 = 3 + 2 = 5
3
a = a3 + a2 = 5 + 3 = 8
4
a = a4 + a3 = 8 + 5 = 13
5
…
This sequence satisfies the same recurrence
relation as the Fibonacci sequence.
Since a = f and a = f , we have a = f .
1 3 2 4 n n+2
15
SOLVING RECURRENCE RELATIONS
In
general, we would prefer to have an
explicit formula to compute the value of an
rather than conducting n iterations.
Forone class of recurrence relations, we can
obtain such formulas in a systematic way.
Those are the recurrence relations that
express the terms of a sequence as linear
combinations of previous terms.
16
SOLVING RECURRENCE RELATIONS
Definition: A linear homogeneous recurrence
relation of degree k with constant
coefficients is a recurrence relation of the form
an = c1an-1 + c2an-2 + … + ckan-k,
where c1, c2, …, ck are real numbers, and ck 0.
A sequence satisfying such a recurrence relation
is uniquely determined by the recurrence relation
and the k initial conditions
a = C0, a1 = C1, a2 = C2, …, ak-1 = Ck-1.
0
17
SOLVING RECURRENCE RELATIONS
Examples:
The recurrence relation Pn = (1.05)Pn-1
is a linear homogeneous recurrence relation
of degree one. Xn = (1.05) x(n-1).i.e. x= 1.05
The recurrence relation fn = fn-1 + fn-2
is a linear homogeneous recurrence relation
of degree two. xn = x(n-1) + x(n-2). x2= x + 1
Therecurrence relation an = an-5 is a linear
homogeneous recurrence relation of degree
five. x5 = 1
18
SOLVING RECURRENCE RELATIONS
Basically, when solving such recurrence relations, we
try to find solutions of the form an = rn, where r is a
constant.
a = rn is a solution of the recurrence relation
n
an = c1an-1 + c2an-2 + … + ckan-k if and only if
rn = c1rn-1 + c2rn-2 + … + ckrn-k.
Divide this equation by rn-k
rk - c1rk-1 - c2rk-2 - … - ck-1r - ck = 0
Thisis called the characteristic equation of the
recurrence relation.
19
SOLVING RECURRENCE RELATIONS
The solutions of this equation are called the
characteristic roots of the recurrence relation.
Let us consider linear homogeneous recurrence
relations of degree two.
Theorem: Let c1 and c2 be real numbers. Suppose
that r2 – c1r – c2 = 0 has two distinct roots r1 and r2.
Then the sequence {an} is a solution of the
recurrence relation an = c1an-1 + c2an-2 if and only if
an = 1r1n + 2r2n for n = 0, 1, 2, …, where 1 and
2 are constants.
20
SOLVING RECURRENCE RELATIONS
Example: What is the solution of the recurrence
relation an = an-1 + 2an-2 with a0 = 2 and a1 = 7 ?
Solution: an = an-1 + 2an-2 r^n = r^(n-1) +2* r^(n-2)
r^2 =r^1 +2
The characteristic equation of the recurrence
relation is r2 – r – 2 = 0.
Its roots are r = 2 and r = -1.
Hence, the sequence {a } is a solution to the
n
recurrence relation if and only if:
a = 2n + (-1)n for some constants and .
n 1 2 1 2
21
SOLVING RECURRENCE RELATIONS
Given the equation an = 12n + 2(-1)n and the
initial conditions a0 = 2 and a1 = 7, it follows that
a0 = 2 = 1 + 2
a1 = 7 = 12 + 2 (-1)
Solving these two equations gives us
1 = 3 and 2 = -1.
Therefore, the solution to the recurrence relation
and initial conditions is the sequence {an} with
an = 32n – (-1)n.
22
SOLVING RECURRENCE RELATIONS
an = rn is a solution of the linear homogeneous
recurrence relation
an = c1an-1 + c2an-2 + … + ckan-k
if and only if
rn = c1rn-1 + c2rn-2 + … + ckrn-k.
Divide this equation by rn-k and subtract the
right-hand side from the left:
rk - c1rk-1 - c2rk-2 - … - ck-1r - ck = 0
This is called the characteristic equation of
the recurrence relation.
23
SOLVING RECURRENCE RELATIONS
The solutions of this equation are called the
characteristic roots of the recurrence
relation.
Letus consider linear homogeneous
recurrence relations of degree two.
Theorem: Let c1 and c2 be real numbers.
Suppose that r2 – c1r – c2 = 0 has two distinct
roots r1 and r2.
Then the sequence {a } is a solution of the
n
recurrence relation an = c1an-1 + c2an-2 if and
only if an = 1r1n + 2r2n for n = 0, 1, 2, …,
where 1 and 2 are constants. 24
SOLVING RECURRENCE RELATIONS
Example: Give an explicit formula for the
Fibonacci numbers.
Solution: The Fibonacci numbers satisfy the
recurrence relation fn = fn-1 + fn-2 with initial
conditions f0 = 0 and f1 = 1.
r^n = r^(n-1) + r^(n-2) r^(n-2). r^2 =r^(n-2)
(r+1)
The characteristic equation is r2 – r – 1 = 0.
Its roots are
1+ √5 1− √ 5
𝑟1= ⥂ ,𝑟 2=
2 2
25
SOLVING RECURRENCE RELATIONS
Therefore, the Fibonacci numbers are given by
( ) ( )
𝑛 𝑛
1+ √5 1− √ 5
𝑓 𝑛 =𝛼1 +𝛼 2
2 2
for some constants 1 and 2.
We can determine values for these constants
so that the sequence meets the conditions f0 =
0 and f1 = 1:
𝑓 0 =𝛼1 +𝛼 2=0
𝑓 1=𝛼1( ) (
1+ √ 5
2
+𝛼2
1 −√5
2 )
=1
26
SOLVING RECURRENCE RELATIONS
The unique solution to this system of two equations
and two variables is
1 1
𝛼 1= , ⥂ 𝛼2=−
√5 √5
So finally we obtained an explicit formula for the
Fibonacci numbers:
( ) ( )
𝑛 𝑛
1 1+ √5 1 1− √ 5
𝑓 𝑛= −
√5 2 √5 2
27
SOLVING RECURRENCE RELATIONS
But what happens if the characteristic
equation has only one root?
How can we then match our equation with
the initial conditions a0 and a1 ?
Theorem: Let c1 and c2 be real numbers with
c2 0. Suppose that r2 – c1r – c2 = 0 has only
one root r0.
A sequence {an} is a solution of the recurrence
relation an = c1an-1 + c2an-2 if and only if
an = 1r0n + 2nr0n, for n = 0, 1, 2, …, where 1
and 2 are constants.
28
SOLVING RECURRENCE RELATIONS
Example: What is the solution of the recurrence
relation an = 6an-1 – 9an-2 with a0 = 1 and a1 = 6?
Solution: The only root of r2 – 6r + 9 = 0 is r0 = 3.
Hence, the solution to the recurrence relation is
a = 3n + n3n for some constants and .
n 1 2 1 2
To match the initial condition, we need
a = 1 =
0 1
a1 = 6 = 13 + 23
Solving these equations yields 1 = 1 and 2 = 1.
Consequently, the overall solution is given by
a = 3 n
+ n3 n
.
n
29
30
31
32
t=2
a(n) =c1(2^n)+c2
(n)(2^n)
a(0)=4 4=c1+0
C1=4
a(1)=2 c1 + c2 (2)
12 = 8 + 2 c2
C2 = 2
33
34
CHARACTERISTIC EQN OF A RR IS (X-1)
(X+3)^2=0. FIND SOLN OF THIS RR.
Characteristic eqn of a rr is (x-1) (x+3)^2=0.
x=1, -3, -3
a(n)= A (1^n) + B (-3 ^n) + C n (-3 ^n)
35
CHARACTERISTIC EQN OF A RR IS (X-2) (X+1)^2
(X-4)^3=0. FIND SOLN OF THE GIVEN RR
Characteristic eqn of a rr is (x-2) (x+1)^2 (x-
4)^3=0.
x=2, -1, -1, 4, 4, 4
a(n) = A (2^n) + B (-1 ^n) + C n(-1 ^n) + D
(4^n) + E n(4^n) +F (n^2) (4^n)
36
NON-HOMOGENEOUS RR
a(n)= 2 a(n-1) – homogen
a(n)= 2 a(n-1) +1 – non-homogen
f(n) = constant
f(n) = polynomial in n
f(n) = d^n
a(r) +5a(r-1)+6a(r-2) = 3 r^2
Step 1 - a(r) +5a(r-1)+6a(r-2) = 0
x^r + 5 x^(r-1) + 6 x^(r-2) =0
x^2 + 5x +6 =0 (x+2)(x+3)=0 x=-2, -3
a(n)= A (-2^n) + B(-3 ^n)
37
38
39
40
41
a(r)-5 a(r-1)+6 a(r-2) = 1 ---(1)
Non- homogen RR
Step 1 : find arC
a(r)-5 a(r-1)+6 a(r-2) = 0 ---(2)
Associated homogen RR of (1)
x^r – 5 x^(r-1) + 6 x^(r-2) = 0
X^2 – 5 x + 6 = 0 Characteristic poly of (1)
(x-3)(x-2)=0 x=3, 2
arC= A (3)^r + B (2)^r --- Complementary fn
Step 2: Find PS
42
f(n) = const ap(n) = const
f(n) = d^n ap(n) = K d^(n) if d is not a
char root
f(n) = poly in n ap(n) =
43
44
45
46
a(n) – 4 a(n-2) = 3n ----(1)
Associated homogen RR of (1) is
a(n) – 4 a(n-2) = 0 ----(2)
x^n – 4 x^(n-2) = 0
X^2 – 4 = 0
(x+2)(x-2) = 0
X = 2, -2
Characteristic roots are 2, -2.
47
48
49
50
51
LINEAR NONHOMOGENOUS RECURRENCE RELATIONS
52
53
SOLVE A(N) = 2 A(N-1) +1
a(n) = 2 a(n-1) +1 To find particular
a(n)-2 a(n-1) = 1 ---(1) solution –
(1) is non- homogen RR
f(n) = 1, constant
Associated Homogen RR
anp = K
a(n)-2 a(n-1) = 0 ---(2) an-1p = K
Char poly of (2) is
Substituting in (1)
xn – 2 x(n-1) = 0
K – 2K = 1
X-2 = 0
K = -1
x=2
Total soln of (1)
anh = A (2)n .
a(n) = anh + an-1p
= A (2)n -1
54
SOLVE A(N) + 4 A(N-1) + 4A(N-2)=(5)N;
A(0) =0, A(1)=1.
a(n) + 4 a(n-1) + 4 a(n-2)=(5)n---(1)
(1) is non-homogen RR
Associated homogen RR is
a(n) + 4 a(n-1) + 4 a(n-2)= 0
Char poly of (2) is x^n + 4 x^(n-1) + 4 x^(n-2) = 0
x^2 + 4 x + 4 = 0 i.e. (x+2)^2 = 0 i.e. x=-2, -2
Homogen soln is anh = (A+ B n) (-2)^n
f(n) = (5)n
Particular solution is anp = K (5)n
an-1p = K (5)n-1 ;an-2p = K (5)n-2
55
a(n) + 4 a(n-1) + 4 a(n-2)=(5)n
K (5)n + 4 K (5)n-1+ 4 K (5)n-2=(5)n
K (5 ^2 + 4 * 5 + 4) = 5 ^2
K (49) = 25 K = 25/49
a(n) = anp + anh
= (25/49) (5)n + (A+ B n) (-2)^n
As a(0) = 0, 0 = (25/49) + (A + 0) A=-25/49
As a(1) = 1, 1 = (25/49)*5 + (A +B) (-2)
Solve this to find B. B= $$
a(n) = (25/49) (5)n + ( -25/49 + $$ n) (-2)^n
56
1, 2, 3 hom soln = A(1)^n + B (2)^n + C(3)^n
-1, 2, 2 hom soln = A(-1)^n + (B+Cn) (2)^n
f(n) = const - particular soln = K
F(n) = poly of deg k – particular soln = poly of
deg k
f(n) = (d)^n - particular soln = K (d)^n if d is
not a characteristic root
f(n) = (d)^n - particular soln = (poly of deg
k) (d)^n if d is a characteristic root with
multiplicity k
57
SOLVE A(N) - 5 A(N-1) + 4A(N-2)=(4)N
a(n) -5 a(n-1) + 4 a(n-2)=(4)n---(1)
(1) is non-homogen RR
Associated homogen RR is
a(n) -5 a(n-1) + 4 a(n-2)= 0
Char poly of (2) is x^n -5 x^(n-1) + 4 x^(n-2) = 0
x^2 -5 x + 4 = 0 i.e. (x-4) (x-1)=0 i.e. x=4,1
Homogen soln is anh = A 4^n+ B 1^n =A 4^n+B
f(n) = (4)n
Particular solution is anp = (K1 + K2 n) 4^n
an-1p = (K1 + K2 (n-1)) 4^(n-1) ;
an-2p = (K1 + K2 (n-2)) 4^(n-2)
58
SUMMARY TO FIND PARTICULAR
SOLUTION
f(n) Condition Particular solution
constant a(n) = K, K- const
(d)^n d is not a characteristic root a(n) = K (d)^n
(d)^n d is a characteristic root with a(n) = (Polynomial of
multiplicity m degree m) (d)^n
Polynomial of 1 is not a characteristic root a(n) = (Polynomial of
degree k degree k)
Polynomial of 1 is a characteristic root with a(n) = (Polynomial of
degree k multiplicity m degree k+m)
59
