Substitution Method, Recurrence Relations

1 Substitution Method
Consider a computational problem P and an algorithm that solves P . Let T (n) be the worst-
case time complexity of the algorithm with n being the input size. Let us discuss a few examples
to appreciate how this method works. For searching and sorting, T (n) denotes the number of
comparisons incurred by an algorithm on an input size n.

1.1 Case studies: Searching

1.1.1 Linear Search
Input: Array A, an element x
Question: Is x ∈ A
The idea behind linear search is to search for the given element x linearly (sequentially) in the
given array. A recursive approach to linear search first searches the given element in the first
location and if it is not found, it recursively calls the linear search with the modified array
without the first element. i.e., the problem size reduces by one in the subsequent calls. Let T (n)
be the number of comparisons (time) required for linear search on an array of size n. Note, when
n = 1, T (1) = 1. Then,

T (n) = 1 + T (n − 1) = 1 + · · · + 1 + T (1),

and since T (1) = 1, therefore:

T (n) = (n − 1) + 1 = n,
i.e.:
T (n) = Θ(n).

1.1.2 Binary search

Input: Sorted array A of size n, an element x to be searched
Question: Is x ∈ A
Check whether A[ n2 ] = x. If x > A[ n2 ], then prune the lower half of the array, A[1, . . . , n2 ].
Otherwise, prune the upper half of the array. Therefore, pruning happens at every iteration.
After each iteration, the problem size (array size under consideration) reduces by half. The
recurrence relation is n
T (n) = T + 1,
2
where T (n) is the time required for binary search in an array of size n. Expanding, we get

T (n) = T (k) + 1 + · · · + 1.

Since T (1) = 1, when n = 2k ,

T (n) = T (1) + k = 1 + log2 (n).

log2 (n) ≤ 1 + log2 (n) ≤ 2 log2 (n), ∀n ≥ 2.

1
 T (n) = Θ(log2 (n)).
Similar to binary search, the ternary search compares x with A[n/3] and A[2n/3], and the
problem size reduces to n/3 for the next iteration. Therefore, the recurrence relation is
n
T (n) = T + 2,
3
and T (2) = 2. Note that there are two comparisons done at each iteration, and due to which
the additive factor 2 appears in T (n).
n n n
T (n) = T +2 ⇒ T =T +2
3 3 9
n
⇒ T (n) = T k + 2 + 2 + · · · + 2 (2 appears k times)
3
When n = 3 ,k

T (n) = T (1) + 2 × log3 (n) = Θ(log3 (n)).

Further, we highlight that for k-way search,
n
T (n) = T + (k − 1)
k
where T (k − 1) = k − 1. Solving this,
T (n) = Θ(logk (n)).
Remarks:
1. It is important to highlight that in an asymptotic sense, binary search, ternary search and
k-way search (fixed k) are of the same complexity as
log2 n = log2 3 · log3 n and log2 n = log2 k · logk n.
So,
Θ(log2 n) = Θ(log3 n) = Θ(logk n), for any fixed k.

2. In the above analysis of binary and ternary search, we assumed that n = 2k (n = 3k ). Is

this a valid assumption? Will the above analysis hold good if n ̸= 2k ? There is a simple
fix to handle input samples that are not 2k for any k. If the input array of size n is such
that n ̸= 2k for any k, then we augment the least number of dummy values so that n = 2k
for some k. By doing so, the size of the modified input array is at most 2n. For ternary
search, the array size increases by at most 3n. This approximation does not change our
asymptotic analysis, as the search time would be one more than the actual search time.
That is, instead of log n, we get log 2n, which is log n + 1. However, in an asymptotic
sense, it is still Θ(log n).

1.2 Case studies: Sorting

To sort an array of n elements using find-max (returns maximum) as a black box.
Approach: Repeatedly find the maximum element and remove it from the array. The order
in which the maximum elements are extracted is the sorted sequence. The recurrence for the
above algorithm is,
(n − 1)n
T (n) = T (n − 1) + (n − 1) = T (n − 2) + (n − 2) + (n − 1) = T (1) + 1 + · · · + (n − 1) =
2

T (n) = Θ(n2 )

2
1.2.1 Merge Sort
Approach: Divide the array into two equal sub-arrays and sort each sub-array recursively. Do
the sub-division operation recursively till the array size becomes one. Trivially, the problem size
one is sorted and when the recursion bottoms out, two sub-problems of size one are combined to
get a sorting sequence of size two, further, two sub problems of size two (each one is sorted) are
combined to get a sorting sequence of size four, and so on. We shall see the detailed description
of merge sort when we discuss the divide and conquer paradigm. To combine two sorted arrays
of size n2 each, we need 2 + 2 − 1 = n − 1 comparisons in the worst case. The recurrence for the
merge sort is,
" #
n n n
T (n) = 2T + (n − 1) = 2 2T 2 + − 1 + (n − 1)
2 2 2
n
⇒ 2k T + (n − 2k ) + (n − 2k−1 ) + · · · + (n − 1).
2k
When n = 2k ,
T (n) = 2k T (1) + n + · · · + n − 2k−1 + · · · + 20 .

Note that
2k − 1
2k−1 + · · · + 20 = = 2k − 1 = n − 1.
2−1
Also, T (1) = 0 as there is no comparison required if n = 1. Therefore,

T (n) = n log2 (n) − n + 1 = Θ(n log2 (n)).

1.2.2 Heap sort

This sorting is based on a data structure max-heap whose creation incurs O(n) time, which we
shall discuss in detail in a later chapter. For now, let us assume a max-heap is given; to sort an
array, the approach is to delete the maximum element repeatedly (which is at the root), and set
right the heap to satisfy the max-heap property. This property maintenance incurs O(log n) time
for each iteration. The order in which the elements are deleted gives the sorted sequence. The
number of comparisons needed for deleting an element is at most the height of the max-heap,
which is log2 (n). Therefore, the recurrence for heap sort is,

T (n) = T (n − 1) + log2 (n), T (1) = 0

⇒ T (n) = T (n − 2) + log2 (n − 1) + log2 (n)

By substituting further,

⇒ T (n) = T (1) + log 2 + log 3 + log 4 + · · · + log n

⇒ T (n) = log(2 · 3 · 4 · · · n) ⇒ T (n) = log(n!)

⇒ log(n!) ≤ n log n as n! ≤ nn (Stirling’s Approximation)

⇒ T (n) = O(n log2 (n)).

Using Stirling’s approximation, we can also show that

T (n) = Ω(n log n).

3
1.3 Finding Maximum
To find the maximum in an array of n elements, we first assume the first element is the maximum
and start comparing this local maximum with the rest of the elements linearly. Update the local
maximum, if required. The base case: T (2) = 1 or T (1) = 0.
Let T (n) denote the worst-case number of comparisons to find the maximum, then

T (n) = T (n − 1) + 1

and the solution is

T (n) = n − 1.
Thus,
T (n) = Θ(n).

2 Change of Variable Technique

√
Problem 1: T (n) = 2T ( n) + 1, T (1) = 1

Introduce a change of variable by letting n = 2m .

⇒ T (2m ) = 2 × T (2m/2 ) + 1

⇒ T (2m ) = 2 × T (2m/2 ) + 1
Let us introduce another change by letting S(m) = T (2m ).

⇒ S(m) = 2 × S(m/2) + 1


⇒ S(m) = 2 × 2 × S(m/4) + 1 + 1
⇒ S(m) = 22 × S(m/22 ) + 2 + 1
By substituting further,

⇒ S(m) = 2k × S(m/2k ) + 2k−1 + 2k−2 + · · · + 2 + 1

To simplify the expression, assume m = 2k .

⇒ S(m/2k ) = S(1) = T (2).

Since T (n) denotes the number of comparisons, it has to be an integer always. Therefore,
√
T (2) = 2 × T ( 2) + 1 ≈ 3.

⇒ S(m) = 3 + 2k − 1 = m + 2.
We now have S(m) = T (2m ) = m + 2. Thus,

T (n) = m + 2, since m = log n, T (n) = log n + 2.

Therefore,
T (n) = Θ(log n).

√
Problem 2: T (n) = 2T ( n) + n, T (1) = 1

Let n = 2m .
⇒ T (2m ) = 2 × T (2m/2 ) + 2m

4
Let S(m) = T (2m ).
⇒ S(m) = 2 × S(m/2) + 2m
⇒ S(m) = 2 × 2 × S(m/4) + 2m/2 + 2m

⇒ S(m) = 22 × S(m/22 ) + 2 · 2m/2 + 2m

By substituting further, we see that

⇒ S(m) = 2k × S(m/2k ) + 2k−1 · 2m + 2k−2 · 2m + · · · + 2 · 2m + 1 · 2m

An easy upper bound for the above expression is

S(m) ≤ 2k · S(m/2k ) · 2m + 2m 2k−1 + 2k−2 + · · · + 2 + 1 .

To simplify, assume m = 2k .

⇒ S(m) ≤ 2k S(1) · 2m + 2m (2k − 1).

Since S(1) = T (21 ) = T (2) ≈ 4,

S(m) ≤ 4m2m + 2m (m − 1).

Hence,
S(m) = O(m2m ), T (2m ) = O(m2m ), T (n) = O(n log n).
Is it true that T (n) = Ω(n log n)? Answer: [Link]: From the first term of the above

expression, it is clear that S(m) ≥ 2m . Therefore,

T (n) = Ω(2m ) = Ω(n).

In a later section, we show that the solution to this recurrence is

Θ(2m ) = Θ(n).

√
Problem 3: T (n) = 2T ( n) + log n, T (1) = 1
Let n = 2m .
⇒ T (2m ) = 2T (2m/2 ) + log(2m )
⇒ T (2m ) = 2T (2m/2 ) + m
Let S(m) = T (2m ).
⇒ S(m) = 2S(m/2) + m


⇒ S(m) = 2 2S(m/4) + m/2 + m
⇒ S(m) = 22 S(m/22 ) + m + m
By substituting further,

⇒ S(m) = 2k S(m/2k ) + m + m + · · · + m

Let m = 2k . Then S(m/2k ) = S(1) = T (2) = 2.

⇒ S(m) = 2 + m(k − 1) + m = 2 + mk

⇒ S(m) = 2 + m log m
⇒ S(m) = O(m log m)
⇒ S(m) = T (2m ) = T (n) = O(log n · log log n).

5
3 Recursion Tree Method
While substitution method works well for many recurrence relations, it is not a suitable tech-
nique for recurrence relations that model divide and conquer paradigm based algorithms. The
Recursion Tree Method is a popular technique for solving such recurrence relations, in particular
for solving unbalanced recurrence relations.
For example, in case of modified merge sort, to solve a problem of size n (to sort an array of
size n), the problem is divided into two problems of size n3 and 2n
3 each. This is done recursively
until the problem size becomes 1.
Consider the following recurrence relation:

1. T (n) = 2T n2 + 1

Here, the number of leaves = 2log n = n and the sum of effort in each level except leaves
is:

log2 (n)−1
X
2i = 2log2 (n) − 1 = n − 1
i=0

Therefore, the total time = n + n − 1 = 2n − 1 = Θ(n).

2. T (n) = 2T n2 + 1, T (1) = log n

Solution: Note that T (1) = log n.

Given, h i
T (n) = 2T n2 + 1 = 2 2T n4 + 1 + 1 = 22 T 2n2 + 2 + 1

h i
= 22 2T 2n3 + 1 + 2 + 1 = 23 T 2n3 + 22 + 2 + 1

⇒ T (n) = 2k T 2nk + 2k−1 + 2k−2 + · · · + 2 + 1

We stop the recursion when n

2k
= 1.

⇒ T (n) = 2k T (1) + 2k − 1 = 2k log n + 2k − 1

= 2log2 n log n + 2log2 n − 1 = n log n + n − 1

Clearly, n log n is the significant term.

T (n) = Θ(n log n).

6
3. T (n) = 3T n4 + cn2

Solution: Note that the number of levels = log4 n + 1.

Also, the number of leaves = 3log4 n = nlog4 3 .

The total cost taken is the sum of the cost spent at all leaves and the cost spent at each
subdivision operation. Therefore, the total time taken is

3 2 3 log4 (n)−1
T (n) = cn2 + 3
cn2 + cn2 cn2 + (number of leaves) × T (1).




16 16 + ··· + 16

 
log4 (n)−1
3 i
X
T (n) = cn2  + nlog4 (3) × T (1).


16
i=0

3 log4 (n)


2 1−
= cn · 16
3 + nlog4 (3) × T (1).
1 − 16
  1
= d · cn2 1 − nlog4 (3)−2 + nlog4 (3) × T (1), where d = 3 .
1 − 16

= dcn2 − dcnlog4 3 + nlog4 (3) × T (1).

≤ dcn2 .

Therefore,
T (n) = O(n2 ).

Since the root of the computation tree contains cn2 ,

T (n) = Ω(n2 ).

Therefore,
T (n) = Θ(n2 ).

7
4. T (n) = T n3 + T 2n



3 + O(n)
Solution: Note that the leaves are between the levels log3 n and log3/2 n.
From the computation tree, it is clear that the maximum height is log3/2 n. Therefore, the
cost is at most
log3/2 n · cn = O(n log n).
Similarly, the minimum height is log3 n. Therefore, the cost is at least

log3 n · cn = Ω(n log n).

Thus,
T (n) = Θ(n log n).

Aliter:
2n
+ O(n) and T (n) ≥ 2T n



T (n) ≤ 2T 3 3 + O(n).

The solution to the former is  

O nlog3/2 2 ,

and the latter is

Ω(n).

5. T (n) = T n 9n



10 +T 10 +n

Solution: Note that the leaves of the computation tree are found between levels log10 n
and log10/9 n.
Assume all the leaves are at level log10 n. Then

T (n) ≥ n log10 n ⇒ T (n) = Ω(n log n).

Assume all the leaves are at level log10/9 n. Then

T (n) ≤ n log10/9 n ⇒ T (n) = O(n log n).

Therefore, we conclude
T (n) = Θ(n log n).

8
4 Master Theorem
We shall now look at a method called the master theorem which is a “cook book” for many
well-known recurrence relations. It presents a framework and formulae using which solutions to
many recurrence relations can be obtained very easily. Almost all recurrences of type

T (n) = aT nb + f (n)

can be solved easily by doing a simple check and identifying one of the three cases mentioned in
the following theorem. By comparing nlogb a (the number of leaves) with f (n), one can decide
upon the time complexity of the algorithm.
Master Theorem: Let a ≥ 1 and b > 1 be constants, let f (n) be a non-negative function,
and let T (n) be defined on the non-negative integers by the recurrence

T (n) = aT nb + f (n),

where we interpret n/b to be either ⌊n/b⌋ or ⌈n/b⌉. Then T (n) has the following asymptotic
bounds:

• Case 1: If f (n) = O(nlogb a−ϵ ) for some constant ϵ > 0, then

 
T (n) = Θ nlogb a .

• Case 2: If f (n) = Θ(nlogb a ), then

 
T (n) = Θ nlogb a log n .

• Case 3: If f (n) = Ω(nlogb a+ϵ ) for some constant ϵ > 0, and if af (n/b) ≤ cf (n) for some
constant c < 1 and all sufficiently large n, then

T (n) = Θ(f (n)).

In the next section, we shall solve recurrence relations by applying the Master Theorem.
Later, we discuss a proof of the theorem and some technicalities to be understood before apply-
ing it.

Examples:

1. T (n) = 9T (n/3) + n
nlogb a = nlog3 9 = n2 , f (n) = n.
Since n = O(n2 ), Case 1 applies:

T (n) = Θ(nlogb a ) = Θ(n2 ).

2. T (n) = T (2n/3) + 1
nlogb a = nlog3/2 1 = n0 = 1 = f (n).
Case 2 applies:
T (n) = Θ(nlogb a log n) = Θ(log n).

3. T (n) = 2T (n/2) + n
nlogb a = nlog2 2 = n, f (n) = n.
Case 2 applies:
T (n) = Θ(nlogb a log n) = Θ(n log n).

9
4. T (n) = 3T (n/4) + n log n
nlogb a = nlog4 3 , f (n) = n log n.
Since f (n) = Ω(nlogb a+ϵ ), Case 3 applies.
Regularity check:
n
af (n/b) = 3 · 4 log n4 ≤ cn log n (c = 3/4).

Hence,
T (n) = Θ(f (n)) = Θ(n log n).

5. T (n) = 4T (n/2) + n
nlogb a = nlog2 4 = n2 , f (n) = n.
Since n = O(n2 ), Case 1 applies:

T (n) = Θ(nlogb a ) = Θ(n2 ).

6. T (n) = 4T (n/2) + n2
nlogb a = nlog2 4 = n2 = f (n).
Case 2 applies:
T (n) = Θ(nlogb a log n) = Θ(n2 log n).

7. T (n) = 2T (n/2) + 2n
nlogb a = nlog2 2 = n, f (n) = 2n.
Clearly f (n) = Ω(nlog2 2+ϵ ). Case 3 applies.
Regularity check:
af (n/b) = 2 · (n/2) = n ≤ c · 2n (c = 1/2).

Hence,
T (n) = Θ(f (n)) = Θ(2n).

8. T (n) = 2T (n/2) + n3n

nlogb a = nlog2 2 = n, f (n) = n3n .
Since f (n) = Ω(nlog2 2+ϵ ), Case 3 applies.
Regularity check:
af (n/b) = 2 · (n/2)3n/2 ≤ c · n3n , (c = 1/3).

Hence,
T (n) = Θ(f (n)) = Θ(n3n ).

Technicalities:

• From the above examples, it is clear that in each of the three cases, we compare the function
f (n) with the function nlogb a . Intuitively, the larger of the two functions determines the
solution to the recurrence.

– If, as in Case 1, the function nlogb a is the larger, then the solution is T (n) = Θ(nlogb a ).
– If, as in Case 3, the function f (n) is the larger, then the solution is T (n) = Θ(f (n)).
– If, as in Case 2, the two functions are the same size, we multiply by a logarithmic factor
which comes from the height of the tree, and the solution is T (n) = Θ(nlogb a log n).

10
• Also, in the first case, not only must f (n) be smaller than nlogb a , it must be polynomially
smaller. That is, f (n) must be asymptotically smaller than nlogb a by a factor of nϵ for
some constant ϵ > 0.
• In the third case, not only must f (n) be larger than nlogb a , it also must be polynomially
larger and in addition, satisfy the regularity condition that af (n/b) ≤ cf (n) for some
c < 1.
• Note that the three cases do not cover all the possibilities for f (n). There is a gap between
Case 1 and Case 2 when f (n) is smaller than nlogb a but not polynomially smaller.
• Similarly, there is a gap between Case 2 and Case 3 when f (n) is larger than nlogb a but not
polynomially larger. If the function f (n) falls into one of these gaps, or if the regularity
condition in Case 3 fails to hold, we cannot use the Master Theorem to solve the recurrence.
• We shall next discuss recurrence relations that fall into the gaps between Case 1 and 2,
and Case 2 and 3. We also look at a recurrence relation that satisfies Case 3 of the Master
Theorem but fails to satisfy the regularity condition.
Examples:

1. T (n) = 2T (n/2) + log n

Here, nlogb a = nlog2 2 = n. If we compare n and f (n) = log n, then n is asymptotically
larger than log n but not polynomially larger. That is,
n
̸= nϵ , ϵ > 0.
log n
Therefore, this recurrence relation falls into the gap between Case 1 and 2 and hence the
Master Theorem is not applicable. This can be solved using the recursion tree method.
2. T (n) = 2T (n/2) + n
n4
Here, nlogb a = = n. Comparing n and f (n) = nn4 = n−3 , we see that n is asymp-
nlog2 2
totically and polynomially larger. Therefore, Case 1 of Master Theorem applies:

T (n) = Θ(n).

3. T (n) = 2T (n/2) + 2
n
Here, nlogb a = = n. Comparing n and f (n) = n2 , we see that n is asymptotically
nlog2 2
and polynomially larger. Therefore, Case 1 of Master Theorem applies:

T (n) = Θ(n).

4. T (n) = 2T (n/2) + n log n Here, nlogb a = nlog2 2 = n. Comparing n and f (n) = n log n, we
find:
• Case 1 does not apply since f (n) is not polynomially smaller.
• Case 2 does not apply since f (n) ̸= Θ(n).
• Case 3 does not apply since f (n) is larger than n, but only by a log n factor, not
polynomially larger.
Therefore, the Master Theorem cannot be applied here.
5. T (n) = 4T (n/2) + n2 log n
Here, nlogb a = nlog2 4 = n2 , while f (n) = n2 log n. Again, f (n) is asymptotically larger
than n2 but not polynomially larger. Hence, the Master Theorem cannot be applied.

11
6. T (n) = 2T (n/2) + n2 n1+sin(n)
Since sin(n) ∈ [−1, 1], we have f (n) ∈ [n2 , n4 ]. Since f (n) is polynomially larger than
nlog2 2 = n, this recurrence seems to satisfy Case 3.
However, it fails
√
the regularity condition. For example, at n = 270, sin(270◦ ) = −1 and
sin(135◦ ) = 22 , the inequality
af (n/b) ≤ cf (n)
fails for any c < 1. Therefore, Master Theorem cannot be applied.
Special Solutions via Recursion Tree:
1. T (n) = 2T (n/2) + log n
Contribution per level: log n, log(n − 1), log(n − 2), . . . (for log n levels).
Lower bound: T (n) ≥ log n + · · · + log n = Ω(n).
Upper bound: T (n) ≤ log(n − h) + · · · + log(n − h), with h = log n.
Hence,
T (n) = Θ(n).
2+sin(n)
2. T (n) = 2T (n/2) + n
Since 2 + sin(n) ∈ [1, 3] and there are log n levels,
T (n) = Θ(n log n).

3. T (n) = 2T (n/2) + n2 n1+sin(n)

Since sin(n) ∈ [−1, 1], we have f (n) ∈ [n2 , n4 ].
Therefore,
Ω(n2 ) ≤ T (n) ≤ O(n4 ).

Remarks

1. Consider the recurrence relation

n


T (n) = 16T 4 + n.
Clearly, Case 1 of Master’s Theorem applies and hence
T (n) = Θ(n2 ).
Let us get a deeper understanding of how nlogb a dominates f (n), af (n/b), and so on.
For this recurrence, f (n) is smaller than nlogb a by nϵ=1 . Interestingly, the contribution
from the subsequent levels is at most n · nϵ=1 .
That is, the cost of the computation tree is
T (n) = n + 4n + 42 n + · · · + n4log n−1 + nlog4 16 .

4log4 n − 1
 
=n + nlog4 16 .
4−1

≤ cn · nϵ=1 + nlog4 16 = O(n2 ).

This shows that nlog4 16 is the dominant factor and the total contribution from all other
levels is at most the number of leaves.

12
 2. Let
n


T (n) = 4T 4 + n.
This satisfies Case 2 of Master’s Theorem and hence, the solution is

Θ(n log n).

From the computation tree, the number of levels is log4 n and each level incurs cost n,
thus
T (n) = Θ(n log n).

Moreover, the contribution from the leaves is just n, which is the same as f (n) = n. Since
the contribution from each level cannot be overlooked in this case, the solution includes
the number of levels and their contribution.

3. Consider
n
+ n2 .


T (n) = 2T 2

In this case, the contribution from each level is cf (n), where c < 1, and the contribution
from the leaves is polynomially smaller than f (n).
This shows that the solution is simply

T (n) = Θ(f (n)) = Θ(n2 ).

4. Note that the regularity condition check demands a constant c < 1. If c = 1 or any fixed
value, then the recurrence falls into Case 2. If c > 1 is a constant and increases with
polynomial growth (c, c2 , c3 , . . .) at each stage, then the recurrence falls into Case 1 of
Master’s Theorem.

4.1 Proof of Master’s Theorem

We shall next present the proof of Master’s Theorem using two Lemmas. As mentioned earlier,
the time complexity T (n) consists of the sum of the cost of leaves and the cost at internal nodes.
The cost at internal nodes is captured using the function g(n) as defined in Lemma 2. Further,
the bounds for g(n) are discussed in Lemma 2 by comparing g(n) and nlogb a .
Lemma 1. Let a ≥ 1 and b > 1, let f (n) be a non-negative function defined on exact powers
of b. Define T (n) on exact powers of b by the recurrence
(
Θ(1), if n = 1,
T (n) =
aT b + f (n), if n = bi .
n

Then,
logb n−1
X
T (n) = Θ(nlogb a ) + aj f n


bj
.
j=0

Proof:

13
 From the recursion tree, it is clear that at level i, there are ai subproblems each of complexity
f (n/bi ). The last level contains the set of leaves and the number of leaves is:

alogb n = nlogb a .

Therefore, the total cost is

logb n−1
X
logb a
aj f n


T (n) = Θ(n )+ bj
.
j=0

Lemma 2. Let a ≥ 1 and b > 1 be constants, let f (n) be a non-negative function defined
on exact powers of b. Define a function g(n) over exact powers of b by
logb n−1
X
aj f n


g(n) = bj
.
j=0

Then g(n) can be bounded asymptotically for exact powers of b as follows:

1. If f (n) = O(nlogb a−ϵ ) for some constant ϵ > 0, then

g(n) = O(nlogb a ).

2. If f (n) = Θ(nlogb a ), then

g(n) = Θ(nlogb a log n).

3. If af (n/b) ≤ cf (n) for some constant c < 1 and for all n ≥ b, then

g(n) = Θ(f (n)).

Proof: Here we analyse the recurrence relation under the simplifying assumption that T (n) is
defined only on exact powers of b > 1, that is, for n = 1, b, b2 , . . .. From Lemma 1,
logb n−1
X
logb a
aj f n


T (n) = Θ(n )+ bj
.
j=0

∞
X 1
g(n) ≤ cj f (n) ⇒ g(n) ≤ f (n) × ⇒ g(n) = O(f (n)).
1−c
j=0
Plogb n−1
Since g(n) = f (n) + j=1 aj f (n/bj ), g(n) > f (n) and g(n) = Ω(f (n)).

g(n) = Θ(f (n))

T (n) = Θ(nlogb a ) + Θ(f (n))

Since f (n) = Ω(nlogb a+ϵ ),
T (n) = Θ(f (n))
This completes a proof of the Master’s theorem.
Not all recurrence relations can be solved using the recursion tree, master’s theorem and
substitution method. We here mention a method of difference equation to solve homogeneous
recurrence relations. That is, recurrence relations which depend on r previous iterations (terms).
Particularly, recurrence relations of the form T (n) = c1 T (n − 1) + c2 T (n − 2) + · · · + cr T (n − r).
In the next section, we shall discuss a method for solving well-known recurrences like Fibonacci
series using the ‘characteristic equation‘ based approach.

14
4.2 Solution using Characteristic Equation Approach
1. an − 7an−1 + 10an−2 = 4n
T (n) − 7T (n − 1) + 10T (n − 2) = 4n
Characteristic equation is x2 − 7x + 10 = 0
(x − 5)(x − 2) = 0; x = 5, 2
Complementary function (C.F.) is c1 5n + c2 2n
Solution is an = c1 5n + c2 2n + Particular integral (P.I.)
For finding P.I., guess an = d4n
d4n − 7d4n−1 + 10d4n−2 = 4n
7d 10d
d− 4 + 16 = 1 ⇒ d = −8
Therefore solution is T (n) = c1 5n + c2 2n − 8 · 4n

2. an − 4an−1 + 4an−2 = 2n
T (n) − 4T (n − 1) + 4T (n − 2) = 2n
Characteristic equation is x2 − 4x + 4 = 0 and the roots are x = 2, 2
Complementary function (C.F.) is c1 2n + c2 n2n
For P.I., note that the guesses d · 2n and d · n2n will not work as the roots and base of the
exponent (non-homogeneous) term are same. Therefore we guess dn2 · 2n .
dn2 2n − 4d(n − 1)2 2n−1 + 4d(n − 2)2 2n−2 = 2n
dn2 − 2d(n2 − 2n + 1) + d(n2 − 4n + 4) = 1
Simplifying we get d = 1
2
n2 n
Therefore T (n) = c1 2n + c2 n2n + 2 2

5 Linear Homogeneous Recurrence Relations

Definition 1. A linear homogeneous recurrence relation of degree k with constant coefficients
is a recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k ,

where c1 , c2 , . . . , ck are real numbers, and ck ̸= 0.

A sequence satisfying a recurrence relation above is uniquely defined by the recurrence rela-
tion and the k initial conditions:

a0 = C0 , a1 = C1 , ..., ak−1 = Ck−1 .

Theorem 1. Let c1 and c2 be real numbers. Suppose that r2 − c1 r − c2 = 0 has two distinct
roots r1 and r2 . Then the sequence {an } is a solution of the recurrence relation

an = c1 an−1 + c2 an−2

if and only if
an = α1 r1n + α2 r2n , for n = 0, 1, 2, . . . ,
where α1 and α2 are constants.

Proof Sketch:

15
 1. First, we prove that, for any constants α1 , α2 , the expression α1 r1n + α2 r2n satisfies the
recurrence relation.

2. Second, we prove that every solution is of the form α1 r1n +α2 r2n . Suppose {an } is a solution
of the recurrence relation with initial conditions a0 = C0 and a1 = C1 . Then, by picking
suitable constants α1 , α2 , we can set the first two values of the sequence α1 r1n + α2 r2n to be
C0 and C1 . Since the sequences {an } and {α1 r1n + α2 r2n } satisfy the degree 2 recurrence
and agree on the first two values, they must be identical.
Example: Find the solution to the recurrence relation an = an−1 + an−2 with initial conditions
a0 = 2 and a1 = 7.

Solution: The characteristic equation is

r2 − r − 2 = 0, i.e. (r − 2)(r + 1) = 0.

The roots are 2 and −1. Thus, the solution to the recurrence relation is of the form

an = α1 2n + α2 (−1)n .

Since this must satisfy the initial conditions, we get

a0 = 2 = α 1 + α 2 ,

a1 = 7 = 2α1 − α2 .
Solving, we get α1 = 3 and α2 = −1.

Thus, the solution to the recurrence relation is an = 3 · 2n − (−1)n . Theorem 2. Let c1

and c2 be real numbers. Suppose that r2 − c1 r − c2 = 0 has only one root r0 . A sequence {an }
is a solution of the recurrence relation

an = c1 an−1 + c2 an−2

if and only if
an = α1 r0n + α2 n · r0n , n = 0, 1, 2, . . . ,
where α1 and α2 are constants. Example: Solve the recurrence relation an = 6an−1 − 9an−2 ,
with initial conditions a0 = 1 and a1 = 6. Solution:

an = 3n + n3n (steps omitted).

Theorem 3. Let c1 , c2 , . . . , ck be real numbers. Suppose that the characteristic equation

rk − c1 rk−1 − · · · − ck = 0

has k distinct roots r1 , r2 , . . . , rk . Then, a sequence {an } is a solution of the recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k

if and only if
an = α1 r1n + α2 r2n + · · · + αk rkn , n = 0, 1, 2, . . . ,
where α1 , α2 , . . . , αk are constants.

Theorem 4. Let c1 , c2 , . . . , ck be real numbers. Suppose that the characteristic equation

rk − c1 rk−1 − · · · − ck = 0

16
has t distinct roots r1 , r2 , . . . , rt with multiplicities m1 , m2 , . . . , mt respectively, so that mi ≥ 1
for i = 1, 2, . . . , t and m1 + m2 + · · · + mt = k. Then, a sequence {an } is a solution of the
recurrence relation
an = c1 an−1 + c2 an−2 + · · · + ck an−k
if and only if

an = (α1,0 + α1,1 n + · · · + α1,m1 −1 nm1 −1 )r1n

+ (α2,0 + α2,1 n + · · · + α2,m2 −1 nm2 −1 )r2n
+ ···
+ (αt,0 + αt,1 n + · · · + αt,mt −1 nmt −1 )rtn ,

for n = 0, 1, 2, . . ., where αi,j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ mi − 1.

Problem: Solve the recurrence relation an = −3an−1 − 3an−2 − an−3 with initial conditions
a0 = 1, a1 = −2, a2 = −1.

Solution:
an = (1 + 3n − 2n2 )(−1)n (steps omitted).

6 Linear Nonhomogeneous Recurrence Relations with Constant

Coefficients
Definition 2. A linear nonhomogeneous recurrence relation with constant coefficients is a
recurrence relation of the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n),

where c1 , c2 , . . . , ck are real numbers, and F (n) is a function not identically zero depending only
on n.

The recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k
is called the associated homogeneous recurrence relation.
A particular solution of a recurrence relation is a sequence that satisfies the recurrence equa-
tion; however, it may or may not satisfy the initial conditions.
(p)
Theorem 5. If {an } is a particular solution of the nonhomogeneous linear recurrence re-
lation with constant coefficients

an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n),

Then every solution is of the form

a(p) (h)
n + an ,
(h)
where an is a solution of the associated homogeneous recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k .

(p)
Proof Sketch: Since {an } is a particular solution of (1),
(p) (p) (p)
a(p)
n = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n). (2)

17
 Let {bn } be an arbitrary solution to the nonhomogeneous recurrence relation. Then,

bn = c1 bn−1 + c2 bn−2 + · · · + ck bn−k + F (n). (3)

Subtracting (2) from (3), we get

(p) (p) (p)
(bn − a(p)
n ) = c1 (bn−1 − an−1 ) + c2 (bn−2 − an−2 ) + · · · + ck (bn−k − an−k ).

(p)
Thus, bn − an is a solution to the associated homogeneous recurrence relation with constant
coefficients.

The above theorem gives us a technique to solve nonhomogeneous recurrence relations us-
ing our tools to solve homogeneous recurrence relations. Given a non-homogeneous recurrence
relation, we first guess a particular solution. Note that this satisfies the recurrence equation,
but does not necessarily satisfy the initial conditions. Next, we use the fact that the required
solution to the recurrence relation is the sum of this particular solution and a solution to the
associated homogeneous recurrence relation. We already know a general form for the solution
to the homogeneous recurrence relation (from the previous theorems). This general form will
have some unknown constants and their values can be determined from the fact that the sum
of the particular solution and the homogeneous solution must satisfy the given initial conditions.

Example: Solve the recurrence relation an = 3an−1 + 2n, with initial condition a1 = 3.

Solution:
an = −n − 3
2 + 11
6 · 3n (steps omitted).
Next, we give a systematic way to guess a particular solution for a large class of functions
F (n).

Theorem 6. Suppose that {an } satisfies the linear nonhomogeneous recurrence relation

an = c1 an−1 + c2 an−2 + · · · + ck an−k + F (n),

where c1 , c2 , . . . , ck are real numbers and

F (n) = (bt nt + bt−1 nt−1 + · · · + b1 n + b0 )sn ,

where b0 , b1 , . . . , bt and s are real numbers.

• When s is not a root of the characteristic equation of the associated linear homogeneous
recurrence relation, there is a particular solution of the form

(pt nt + pt−1 nt−1 + · · · + p1 n + p0 )sn .

• When s is a root of this characteristic equation and its multiplicity is m, there is a particular
solution of the form
nm (pt nt + pt−1 nt−1 + · · · + p1 n + p0 )sn .

The above theorem gives a recipe for picking a particular solution to a nonhomogeneous
recurrence relation. The general form of the particular solution has several unknown constants.
Their values can be determined by substituting this general form into the given nonhomogeneous
recurrence relation. This yields a set of equations that can be solved to determine the values of

18
the constants. Substituting the general form yields a single equation. However, this equation
says that a particular expression of the form
t
X
βi fi (n)
i=1

must be identically 0 for all values of n ≥ k. Here βi are linear expressions involving the
unknown constants and fi (n) are functions of n. This then implies that βi = 0 for all i, giving
the required number of equations to determine the unknown constants.

Example: Solve the recurrence relation an = an−1 + n, with initial condition a0 = 0.

Solution:
an = 12 n2 + 21 n (steps omitted).

7 Using generating functions to solve recurrence relations

We associate with the sequence {an }, the generating function
∞
X
a(x) = an xn .
n=0

Now, the recurrence relation for {an } can be interpreted as an equation for a(x). This allows
us to get a formula for a(x) from which a closed form expression for an can be derived.

Example: Find the generating function for the Fibonacci sequence and derive a closed form
expression for the nth Fibonacci number.

Solution: Let
∞
X
F (x) = fn xn ,
n=0

be the generating function for the Fibonacci sequence. Since the Fibonacci sequence satisfies
the recurrence fn = fn−1 + fn−2 , n ≥ 2, we get an explicit form for F (x) as follows:
∞
X ∞
X ∞
X
n n
fn x = fn−1 x + fn−2 xn
n=2 n=2 n=2
∞
X ∞
X ∞
X
n n 2
fn x = x fn x + x fn xn
n=2 n=1 n=0

F (x) − f0 − f1 x = x(F (x) − f0 ) + x2 F (x)

F (x)(1 − x − x2 ) = f0 + x(f1 − f0 ) − x

x
F (x) = .
1 − x − x2
To get a closed-form expression for fn , we need to get a closed-form expression for the
coefficient of xn in the expansion of the generating function. To do this, we use the technique
of decomposition into partial fractions:

19
 x A B
2
= + ,
(1 − x − x ) x − x1 x − x2
where x1 and x2 are the roots of the polynomial 1 − x − x2 . It is more convenient to express
the generating function in the following form:

x a b
2
= + ,
1−x−x 1 − r1 x 1 − r2 x
where r1 = 1/x1 and r2 = 1/x2 . It turns out that r1 and r2 are the roots of the characteristic
equation (verify this). From this, we can get the closed-form expression

fn = a · r1n + b · r2n .

We can solve for a and b from the fact that the initial conditions must be satisfied and this
will give us the result:
" √ !n √ !n #
1 1+ 5 1− 5
fn = √ − .
5 2 2
The above technique can be generalised to get an expression for the solution of a general
homogeneous recurrence relation with constant coefficients considered in Theorem 4.

an = c1 an−1 + c2 an−2 + · · · + ck an−k

Suppose that the characteristic equation

rk − c1 rk−1 − · · · − ck = 0
has t distinct roots r1 , r2 , . . . , rt with multiplicities m1 , m2 , . . . , mt respectively, so that mi ≥
1 for i = 1, 2, . .P
. , t and m1 + m2 + · · · + mt = k.
Let a(x) = ∞ n=0 an x be the generating function associated with the sequence {an }. From
n

the recurrence relation, we can get an expression for a(x) as follows:

an = c1 an−1 + c2 an−2 + · · · + ck an−k (4)

a(x) = (c1 x + c2 x2 + · · · + ck xk )a(x) + b0 + b1 x + · · · + bk−1 xk−1 (5)

Pi
Here bi , i = 0, 1, . . . , k−1 are constants where bi = ai − j=1 cj ai−j . This gives the following
expression for a(x):

b0 + b1 x + · · · + bk−1 xk−1
a(x) = .
1 − c1 x − c2 x2 − · · · − ck xk
We express this using partial fractions. First, we factorise the denominator as follows:

1 − c1 x − c2 x2 − · · · − ck xk = (1 − r1 x)m1 (1 − r2 x)m2 · · · (1 − rt x)mt ,

where r1 , . . . , rt are the roots of the characteristic equation with multiplicities m1 , . . . , mt
respectively. (This is not obvious. Verify this!)

Now, we can write down the following expression for a(x):

b0 + b1 x + · · · + bk−1 xk−1
a(x) =
(1 − r1 x)m1 (1 − r2 x)m2 · · · (1 − rt x)mt

20
 A1,0 A1,1 A1,m1 −1
= m
+ m −1
+ · · · +
(1 − r1 x) 1 (1 − r1 x) 1 (1 − r1 x)
A2,0 A2,1 A2,m2 −1
+ m
+ m −1
+ ··· +
(1 − r2 x) 2 (1 − r2 x) 2 (1 − r2 x)

···

At,0 At,1 At,mt −1

+ m
+ m −1
+ · · · + ,
(1 − rt x) t (1 − rt x) t (1 − rt x)
where Ai,j are constants for 1 ≤ i ≤ t and 0 ≤ j ≤ mi − 1.
Computing the coefficient of xn using the generalised binomial theorem, we get:
   
n+1 n + m1 − 1
an = (A1,0 + A1,1 + · · · + A1,m1 −1 )r1n
1 m1 − 1
   
n+1 n + m2 − 1
+(A2,0 + A2,1 + · · · + A2,m2 −1 )r2n
1 m2 − 1
   
n+1 n + mt − 1
+ · · · + (At,0 + At,1 + · · · + At,mt −1 )rtn .
1 mt − 1
for n = 0, 1, 2, ...

Note that this solution is of a slightly different form than the solution claimed in Theorem
4, but the two forms are equivalent, i.e., one form can be converted to the other.
The generating function approach allows us to solve fairly general recurrence relations, as
illustrated below.

Example: Find an explicit formula for the Catalan numbers defined by the recurrence relation
n−1
X
Cn = Ck Cn−1−k
k=0

where C0 = 1.
P∞
Solution: Let C(x) be the generating function n=0 Cn x
n. Then,
n−1
X
Cn = Ck Cn−1−k .
k=0
Multiplying by xn , we get:
n−1
X
Cn xn = xn Ck Cn−1−k
k=0
n−1
X
Cn x n = x (Ck xk ) · (Cn−1−k xn−1−k ).
k=0
Summing this up from n = 1 to ∞, we get:
∞
X ∞ n−1
X X
n
Cn x = x (Ck xk ) · (Cn−1−k xn−1−k ).
n=1 n=1 k=0

21
 P∞
Note that C(x) = n=0 Cn x
n. Hence,

C(x) − C0 = xC(x)2 ,

xC(x)2 − C(x) + 1 = 0.
Solving this quadratic equation, we get:
√
1 − 4x
1±
C(x) = .
2x
The generating function is uniquely defined by the recurrence relation and the initial condi-
tion C0 = 1. Hence, we should be able to rule out one of the two possibilities. If we choose the +
sign in the expression for C(x), C(x) → ∞ for x → 0. However, for x → 0, C(x) → C0 = 1. This
rules out the + sign as a valid possibility. Thus, the closed-form expression for the generating
function is
√
1 − 1 − 4x
C(x) = .
2x
Using this, we can obtain a closed-form expression for Cn , the nth Catalan number. We could
certainly do this using the generalised binomial theorem. Here, we give an alternate approach.
We know from a previous exercise that
∞  
1 X 2n n
√ = t
1 − 4t n=0 n

Integrating from t = 0 to t = x, we get:

Z x ∞  Z x
1 X 2n
√ dt = tn dt
0 1 − 4t n 0
n=0

√ ∞  
1− 1 − 4x X 1 2n n
= x
2x n+1 n
n=0

Comparing the coefficient of xn on both sides, we get that

 
1 2n
Cn = .
n+1 n

22