Chapter 2

Recurrences

2.1 Karatsuba’s Algorithm: One Example of Recursive

Algorithms
We learned multiplication in primary school. When we do 12 × 34, we essentially calculate
1 × 3 × 100 + (2 × 3 + 1 × 4) × 10 + 2 × 4. In general, we use the formula

n−1 n−1 n−1 Xi 2(n−1) n−1

X X X X X
i i i
( xi · b ) · ( yi · b ) = ( xj yi−j ) · b + ( xj yi−j ) · bi ,
i=0 i=0 i=0 j=0 i=n j=i−(n−1)

where b = 10 for decimal calculations, while b is often equal to some power of 2 in computers.
This naive algorithm needs to do n2 “basic” multiplications (i.e., multiplications over [0, b − 1]) in
order to multiply two number from [0, bn − 1]. Naturally, many people suspected that the above
“textbook multiplication” algorithm might be the best we could do, because there seemed to be
no obvious way to do multiplications faster.
Surprisingly, Karatsuba1 proposed a counter-intuitive algorithm that easily beats the “text-
book multiplication” algorithm. The idea is quite simple: when you do 12 × 34, you should not
waste your time doing two “basic” multiplications for (2 × 3 + 1 × 4). Instead, you should just
calculate (1 + 2) × (3 + 4) − 1 × 3 − 2 × 4, which is identical to (2 × 3 + 1 × 4). Noticing that you
have to calculate 1 × 3 and 2 × 4 for other parts of the expression anyway, for this specific part
1
Anatoly Karatsuba (1937-2008) was a Russian mathematician. When he was a student, he attended Kol-
mogrov’s seminar at the Moscow State University, and proposed an idea for accelerating the multiplication algo-
rithm. Kolmogrov wrote his idea into a paper, with Karatsuba as the sole author, and got it published. As a
professional mathematician, Karatsuba mainly worked on number theory.

73
74 CHAPTER 2. RECURRENCES

you just need to do one “basic” multiplication! Therefore, we have reduced the total amount of
work.
Below we present a straightforward recursive algorithm based on Karatsuba’s idea.
Algorithm: Karatsuba(x, y)
Input: x and y, two positive integers.
Output: the product xy.
if (x < 2b ) or (y < 2b )
return xy;
split x in the middle and get (hx , lx );
split y in the middle and get (hy , ly );
r0 = Karatsuba(lx , ly );
r1 = Karatsuba((lx + hx ), (ly + hy ));
r2 = Karatsuba(hx , hy );
return the number r2 · 22b + (r1 − r2 − r0 ) · 2b + r0 .

Example 2.1.1 Suppose that we are running Karatsuba’s algorithm to compute 0101×0010. (All
numbers in this example, like 0101 and 0010, are binary.) The algorithm recursively calls itself
three times:

• To compute 01 × 10, it recursively calls itself three times:

– It computes 1 × 0 = 0.
– It computes (1 + 0) × (0 + 1) = 1.
– It computes 0 × 1 = 0.

Therefore, it calculates 1 − 0 − 0 = 1 and returns 010 for 01 × 10.

• To compute (01 + 01) × (10 + 00) = 10 × 10, it recursively calls itself three times:

– It computes 0 × 0 = 0.
– It computes (0 + 1) × (0 + 1) = 1.
– It computes 1 × 1 = 1.

Therefore, it calculates 1 − 1 − 0 = 0 and returns 100 for (01 + 01) × (10 + 00).

• To compute 01 × 00, it recursively calls itself three times:

– It computes 1 × 0 = 0.
2.2. RECURRENCES, TOTAL AND PARTICULAR SOLUTIONS 75

– It computes (1 + 0) × (0 + 0) = 0.
– It computes 0 × 0 = 0.

Therefore, it calculates 0 − 0 − 0 = 0 and returns 000 for 01 × 00.

Finally, it calculates 100 − 010 − 000 = 010 and returns 001010 for 0101 × 0010.

Now, assume that each “basic” multiplication is on a couple of b-bit integers, and that Karat-
suba’s algorithm needs T (n) “basic” multiplications on a couple of n-bit numbers. Assuming the
multiplication of lx + hx and ly + hy requires no more “basic” multiplications than the multipli-
cation of lx and ly (or that of hx and hy ), we get the following equation:2
n
T (n) = 3T ( ). (2.1)
2
n
It is trivial to derive from the above equation that T (n) = 3log2 b T (b) = ( nb )log2 3 ≈ nlog2 3 , assuming
b is small and n is big. In contrast, the naive algorithm needs n2 “basic” multiplications. For
large n, the difference can be very significant.
Karatsuba’s algorithm is the beginning of a search for formulas that help reduce the compu-
tational cost of multiplication. Many more formulas have been found since then. For example,
in 2009, Fan et al. developed a number of Karatsuba-like formulas, including some asymmetric
ones. Interested readers can refer to [21].
A more popular algorithm for multiplication (of polynomials in general, and of integers in
particular) is Fast Fourier Transform (FFT), which has an even lower computational cost. Just
like Karatsuba’s algorithm, FFT is also a divide-and-conquer algorithm. A nice introduction to
FFT can be found in standard textbooks of algorithms, like [12].
One might find it interesting to solve recurrence relations like Eq. (6.1). It turns out that
there is no universal approach to solve all recurrence equations. Hereafter, we examine a few
types of recurrences that we know how to solve.

2.2 Recurrences, Total and Particular Solutions

We say a recurrence is linear if T (n) is equal to a linear combination of T (m)s (m < n). For
a large class of linear recurrences, we happen to know the structure of their solutions, which is
quite analogous to that of solutions to linear systems.
2
Hereafter, we are sloppy, using notations like T ( n2 ), despite that T is defined on positive integers but n2 may
not be an integer. In order to be rigorous, we would have to replace n2 with b n2 c, and take care of a lot more
details. To keep it simple, we use expressions like T ( n2 ) as if they were legal.
76 CHAPTER 2. RECURRENCES

Theorem 2.2.1 The set of solutions to the linear recurrence

k
X
T (n) = ci T (ai n + bi ) + d(n), (n ≥ n0 ) (2.2)
i=1

(where ai n + bi < n for all i and all n ≥ n0 ) is

k
X
{T0 (n) + T1 (n)|T0 (n) = ci T0 (ai n + bi )},
i=1

where T1 (n) is an arbitrary solution to Equation (2.2). Since T1 (n) itself belongs to the set of
solutions, we usually call it a particular solution and the set of all solutions the total solution.

Proof: Consider
k
X
T (n) = ci T (ai n + bi ). (2.3)
i=1

Equation (2.3) has all terms being of degree 1, and is thus called a homogeneous equation. Suppose
that T0 (n) is a solution to Equation (2.3), and that T1 (n) is a solution to Equation (2.2). Easy
to get that
k
X k
X
T1 (n) + T0 (n) = ci T1 (ai n + bi ) + d(n) + ci T0 (ai n + bi )
i=1 i=1
Xk
= ci (T1 (ai n + bi ) + T0 (ai n + bi )) + d(n).
i=1

Hence, T1 (n) + T0 (n) must also be a solution to Equation (2.2).

Conversely, if T2 (n) is a solution to Equation (2.2), we can easily verify that T2 (n) − T1 (n) is
a solution to Equation (2.3). Therefore, T2 (n) can be written as the sum of T1 (n), a particular
solution, and a solution to the homogeneous equation. 

Example 2.2.1 Suppose that we would like to solve the recurrence

n
T (n) = 2T ( ) − 1.
2
Clearly the corresponding homogeneous equation has solutions T0 (n) = kn where k is an
arbitrary constant. A particular solution is T1 (n) = 1. Hence, the total solution is T (n) = kn + 1.
2.2. RECURRENCES, TOTAL AND PARTICULAR SOLUTIONS 77

Nevertheless, homogeneous equations are not always so easy to solve. In many cases, we do
not know how to solve it and have to rely on the “guess-and-prove” strategy. Below we discuss
one (unusual) type of homogeneous equations for which we do have a systematic approach.

Definition 2.2.1 Consider the homogeneous equation

T (n) = c1 T (n − 1) + c2 T (n − 2) + . . . + ck T (n − k), (2.4)

where k is a constant positive integer, c1 , . . . , ck are all constants, and c1 ck 6= 0. We say Equa-
tion (2.4) is a linear homogeneous recurrence with constant coefficients of order k. Its character-
istic equation is
xk − c1 xk−1 − c2 xk−2 − . . . − ck = 0. (2.5)

If you have studied linear algebra, please compare the above definition with the characteristic
equation of a real symmetric matrix. If you have studied differential equations, please compare
the above definition with the characteristic equation of a linear differential equation with constant
coefficients of order k. The comparison will help you understand the deep connection between
Equations (2.4) and (2.5), which is reflected by the theorem below.

Theorem 2.2.2 If Equation (2.5) has k distinct roots r1 , . . . , rk , then the solutions to Equa-
tion (2.4) are
T0 (n) = a1 r1n + a2 r2n + . . . + ak rkn ,
where a1 , . . . , ak are constants. There is no other solution to Equation (2.4).

Proof: First, since r1 , . . . , rk are roots of Equation (2.5), for i = 1, . . . , k, we have

rik − c1 rik−1 − c2 rik−2 − . . . − ck = 0 ⇒ rin = c1 rin−1 + c2 rin−2 + . . . + ck rin−k .

Hence,

T0 (n) = a1 r1n + a2 r2n + . . . + ak rkn

= a1 (c1 r1n−1 + c2 r1n−2 + . . . + ck r1n−k ) + . . . + ak (c1 rkn−1 + c2 rkn−2 + . . . + ck rkn−k )
= c1 (a1 r1n−1 + a2 r2n−1 + . . . + ak rkn−1 ) + . . . + ck (a1 r1n−k + a2 r2n−k + . . . + ak rkn−k )
= c1 T0 (n − 1) + . . . + ck T0 (n − k),

which means T0 (n) satisfies Equations (2.4).

Next, we show there is no other solution to Equation (2.4). Suppose S(n) is a solution to
Equation (2.4), i.e.,

S(n) = c1 S(n − 1) + c2 S(n − 2) + . . . + ck S(n − k).

78 CHAPTER 2. RECURRENCES

We need to show that S(n) = T0 (n) for all n, if the coefficients a1 , . . . , ak in T0 (n) are chosen
properly.
To choose the coefficients a1 , . . . , ak in T0 (n), consider the linear system (with unknowns
a1 , . . . , a n )


 a1 r1 + a2 r2 + . . . + ak rk = S(1)
a1 r12 + a2 r22 + . . . + ak rk2 = S(2)


 ...
a1 r1k + a2 r2k + . . . + ak rkk = S(k).


The coefficient matrix of the left hand side can be viewed as the product of a Vandermonde matrix
and a diagonal matrix :
    
r1 r2 . . . rk 1 1 ... 1 r1 0 . . . 0
 r12 r22 . . . rk2   r1 r2 . . . rk    0 r2 . . . 0  .
 
 =
 ... ...   ... ...   ... ... 
k k k k−1 k−1 k−1
r1 r2 . . . rk r1 r2 . . . rk 0 0 . . . rk

We all know that a Vandermonde matrix must be full-rank. We realize that the diagonal ma-
trix must also be full-rank, because the roots r1 , . . . , rk can’t be equal to 0.3 Consequently,
the coefficient matrix must be full-rank, and the linear system must have a (unique) solu-
tion. When we use this solution as the coefficients a1 , . . . , ak in T0 (n), we are guaranteed that
T0 (1) = S(1), T0 (2) = S(2), . . . , T0 (k) = S(k). A simple induction on n allows us to extend this
result to T0 (n) = S(n) for all positive integer n, because both T0 () and S() satisfy the same
recurrence. 

Example 2.2.2 A function T : Z+ → Z+ satisfies the following conditions:

• For all n1 , n2 ∈ Z+ such that gcd(n1 , n2 ) = 1, T (n1 n2 ) = T (n1 )T (n2 ).
(T (mn−1 ))3
• For all m, n ∈ Z+ (n ≥ 2), T (mn ) = (T (mn−2 ))2
.
Find the function T .

(T (p )) n−1 3
Solution: Consider an arbitrary prime p. Since T (pn ) = (T (pn−2 ))2
, defining S(n) = log T (pn ),
we get that S(n) = 3S(n − 1) − 2S(n − 2). The characteristic equation of this recurrence is
x2 − 3x + 2 = 0, which has two distinct roots 1 and 2. Hence, the solution to this recurrence is
S(n) = ap 2n + bp , where ap , bp are constants.
3
If any of the roots is equal to 0, then ck , the constant term of the characteristic equation, must be 0, contra-
dicting our requirement that c1 ck 6= 0.
2.2. RECURRENCES, TOTAL AND PARTICULAR SOLUTIONS 79

From T (1)T (n) = T (n), we easily get that T (1) = 1. Hence S(0) = 0, which means bp = −ap .
n n
Thus, S(n) = ap (2n − 1), i.e., T (pn ) = 2ap (2 −1) = (T (p))2 −1 . For a general positive integer
n n
pn1 1 . . . pnk k where p1 , . . . , pk are primes, T (pn1 1 . . . pnk k ) = (T (p1 ))2 1 −1 . . . (T (pk ))2 k −1 . The value
of T (p) for each prime p can be arbitrarily chosen from positive integers. 
Theorem 2.2.2 perfectly solves Equation (2.4) when the characteristic equation has distinct
roots. But in reality, we often have double roots and triple roots. What can we do then?
Fortunately, we have another theorem that takes care of multiple roots.
Theorem 2.2.3 If Equations (2.5) has ` roots r1 , . . . , r` , where ri is of multiplicity mi for i =
1, . . . , `, then the solutions to Equation (2.4) are
`
X
T0 (n) = (ai,1 + ai,2 n + . . . + ai,mi nmi −1 )rin ,
i=1

where aij s are all constants. There is no other solution to Equation (2.4).
The proof of Theorem 2.2.3 is quite similar to that of Theorem 2.2.2. There are two major
differences:
• Since ri is a root of multiplicity mi , on top of
rik − c1 rik−1 − c2 rik−2 − . . . − ck = 0,
we also have
krik−1 − c1 (k − 1)rik−2 − c2 (k − 2)rik−3 − . . . − ck−1 = 0,
...
k(k − 1) . . . (k − mi + 2)rik−mi +1 − c1 (k − 1) . . . (k − mi + 1)rik−mi − . . . ck−mi +1 (mi − 1)! = 0.
These equations help us to show that T0 (n) satisfies the recurrence.
• A generalization of Vandermonde matrix is confluent Vandermonde matrix [59], which is
also full-rank.
Theorems 2.2.2 and 2.2.3 tell us how to solve homogeneous equations. To get the total solution
of Equation (2.2), we still need to find a particular solution. The bad news is that we do not
have a systematic approach to finding a particular solution. The best we can do is only slightly
better than the guess-and-prove method: the method of undetermined coefficients. It is slightly
better in that we only need to guess what kind of function could be a particular solution, not
the parameters of the function. As long as our guess is correct, the method of undetermined
coefficients can help us correctly calculate the parameters of the function. Below we demonstrate
how the method of undetermined coefficients works.
80 CHAPTER 2. RECURRENCES

Example 2.2.3 Solve the recurrence

e3 e6 e3 + e6 e4
T (n) = T (n − 1) + T (n − 2) + (1 − )en + + e7 .
2 2 2 2

Solution: The characteristic equation is

e3 e6
x2 − x− = 0.
2 2
3
Solving this equation, we get two roots r1 = e3 and r2 = − e2 . Consequently, the solution to the
3
homogeneous equation is T0 (n) = a1 e3n + a2 (− e2 )n , where a1 , a2 are constants.
We guess a particular solution could be linear.4 So we plug T (n) = un + v into the original
equation and get that

e3 e6 e3 + e6 e4
un + v = (u(n − 1) + v) + (u(n − 2) + v) + (1 − )en + + e7
2 2 2 2
e3 + e6 u(e3 + 2e6 ) e3 + e6 e4
⇒u= · (u − e) + e; v=− + · v + + e7
2 2 2 2
Solving the last equation system, we get that u = e, v = 0, which means T1 (n) = en is a particular
solution to the original recurrence. Hence, the total solution is

e3 n
T (n) = T0 (n) + T1 (n) = a1 e3n + a2 (− ) + en.
2

Theorems 2.2.1, 2.2.2, and 2.2.3, give us a very powerful tool to solve recurrences. Together
with methods discussed in future sections, they enable us to solve recurrences in systematics
ways. Nevertheless, these theorems and methods are not all we can use when solving recurrences.
You will always encounter “strange” recurrences that can never be solved in a systematic way.
What can you do in that case? You should bravely guess a solution, just like in the solution of
Example 2.2.3. Below we do another example that requires you to guess (and prove).
√
Example
p 2.2.4 (USAMO 1990, Day 1, Problem 2) Suppose T (1) = x2 + 48 and T (n + 1) =
x2 + 6T (n) for n ≥ 1. Solve the equation T (n) = 2x for all positive integer n and all real
number x.
4
Don’t ask me why. I have no idea about how to make guesses.
2.2. RECURRENCES, TOTAL AND PARTICULAR SOLUTIONS 81

Solution: Obviously n = 1, x = 4 is a solution. Further calculations tell us that, ∀n0 ∈ Z+ ,

n = n0 , x = 4 is a solution. Now we show that there is no other solution. Clearly, x ≥ 0.
If x > 4, then 3x2 > 48 ⇒ 4x2 > x2 + 48 ⇒ T (1) < 2x. For each positive integer n, we have
T (n) < 2x ⇒ x2 + 6T (n) < x2 + 12x < x2 + 3x2 = 4x2 ⇒ T (n + 1) < 2x.
If x < 4, then 3x2 < 48 ⇒ 4x2 < x2 + 48 ⇒ T (1) > 2x. For each positive integer n, we have
T (n) > 2x ⇒ x2 + 6T (n) > x2 + 12x > x2 + 3x2 = 4x2 ⇒ T (n + 1) > 2x.
Consequently, our initial guess of x = 4 (for all positive integer n) is the only solution. 
Sometimes we don’t even have the recurrence available, so that you need to make a guess
about it in the first place.

Example 2.2.5 (IMO 1998 Shortlist C3, Generalized [71]) Cards numbered 1 to n are arranged
at random in a row with n ≥ 5. In a move, one may choose any block of consecutive cards
whose numbers are in ascending or descending order, and switch the block around. For example,
if n = 9, then 9 1 6 5 3 2 7 4 8 may be changed to 9 1 3 5 6 2 7 4 8. Prove that
in at most 2n − 6 moves, one can arrange the n cards so that their numbers are in ascending or
descending order.

Solution: For n ≥ 5, we have the following simple recursive algorithm that can arrange n + 1
cards: First, we do a recursive call to arrange first n cards. Assume that, after the recursive call,
we still need to place the last card between the ith and (i+1)st cards. We use one move to reverse
the order of the (i + 1)st through nth cards; then we use another move to reverse the order of the
(i + 1)st through (n + 1)st cards. Easy to see that we are done after these two additional moves.
(Note that we could have arranged the last n cards and then inserted the first card at the correct
location. In general, two moves are sufficient for inserting the first/last card to n cards that have
already been sorted. )
Denote by T (n) the number of moves needed by the above algorithm (in the worst case), when
the input is n cards. We immediately get that T (n + 1) = T (n) + 2. The total solution to this
recurrence is T (n) = 2n + c, where c is a constant. In order to show that c = −6, we need to
figure out the value of T (5). Obviously, as long as T (5) = 4, we can obtain c = −6. It might
be a bit surprising that showing T (5) = 4, or, equivalently, arranging 5 cards in 4 moves, is not
trivial. To achieve this objective, we distinguish two cases:
Case A: The first or last card is numbered 1 or 5. W. L. O. G., assume the initial configuration
is 1 w x y z. In a single move, we can easily arrange the last three cards in ascending/descending
order. (Do you see how?) Next, we use two moves to insert w to them. After that, if the last four
cards are descending, we use another move to reverse them; otherwise, we do nothing. In total,
we need either 3 or 4 moves.
Case B: Neither 1 nor 5 is the first or the last card. This includes two subcases.
82 CHAPTER 2. RECURRENCES

Subcase B1: One of 1 and 5 is right in the middle. W. L. O. G., assume the initial configuration
is x 1 5 y z. If y < z, then we do two moves: x 1 5 y z → x 1 y 5 z → x 1 y z 5. If
y > z, then we do a single move: x 1 5 y z → x 1 z y 5. After these two/one move, the last
four cards are already sorted in ascending order. Next, we use two additional moves to insert x
to them. So, in total, we have used either 3 or 4 moves.
Subcase B2: Neither 1 nor 5 is right in the middle. W. L. O. G., assume the initial configuration
is x 1 y 5 z. If y < z, then we do a single move: x 1 y 5 z → x 1 y z 5. If y > z, then we
do two moves: x 1 y 5 z → x 1 5 y z → x 1 z y 5. After these one/two moves, the last
four cards are already sorted in ascending order. Next, we use two additional moves to insert x
to them. Again, in total, we have used either 3 or 4 moves. 

2.3 The Generating Function Method

You might have studied, or at least heard of, generating functions, which was first introduced by
de Moivre5 They are a valuable tool in combinatorics. In this section, we start from scratch and
show you how to solve recurrences using generating functions.

Definition 2.3.1 For function T (n) defined on natural numbers6 , its (ordinary) generating func-
tion is
X∞
G(z) = T (i)z i .
i=0

What is the generating function G(z)? Why do we need it? It is just another way to express the
function T (n)—it carries exactly the same information as T (n), although it looks a bit different.
We can easily convert T (n) to its generating function G(z), and vice versa. The advantage of
having another expression of the same mathematical object is that sometimes we can process it
more easily. For example, in certain situations (which we shall see shortly), finding the generating
function of a solution to a recurrence is easier than finding the solution itself. In that case, our
strategy is to figure out the generating function first, and then convert it to the actual solution.
5
Abraham de Moivre (1667-1754) was a French mathematician. When he was a student, he received only
a moderate amount of formal mathematical training through private lessons. But he became a professional
mathematician anyway. Being a protestant, he had to flee to England due to religious persecutions. Living in
England, he was very close to Newton, who claimed that “he knows all these things (mathematics) better than I
do.” In addition to generating functions, de Moivre had another great contribution to mathematics, de Moivre’s
Formula: (cos x + i sin x)n = cos nx + i sin nx.
6
For convenience, we allow n to be equal to 0 here, because otherwise the generating function would not have
a constant term.
88 CHAPTER 2. RECURRENCES

The coefficient of xn on the left hand side must be equal to that on the right hand side:
X n + 1 n + 1  X n + 2 n 
= ,
0≤k≤n
k n−k 0≤k≤n
k n−k

which is clearly equivalent to what we need to show. 

Problem Set 4
Problem 59 [Difficulty Estimate=1.6] Prove that Equation (2.6) has only two solutions,
T (n) = 0 and the one given in Formula (2.7).

Problem 60 [Difficulty Estimate=1.1] To calculate the product of two polynomials f (x) =

ax + b and g(x) = ux2 + vx + w, a naive algorithm needs 6 multiplications of coefficients. How
can you do better?

Problem 61 [Difficulty Estimate=2.1] Prove the number of linearly independent solutions to

Equation (2.4) is equal to the number of distinct roots of its characteristic equation.

Problem 62 [Difficulty Estimate=0.6] Solve the recurrence T (n) = 3T (n − 1) + (−3)n .

Problem 63 (Chapter 1 Exercise 20 of [26]) [Difficulty Estimate=2.4] Solve the recurrence

T (2n) = 4T (n) + an + b, T (2n + 1) = 4T (n) + cn + d, where T (1) = u is given.

Problem 64 [Difficulty Estimate=2.3] Solve the recurrence



 3T (n − 1) − 5T (n − 2) if n ≡ 0 (mod 4)
6T (n − 1) − 5T (n − 4) if n ≡ 1 (mod 4)

T (n) =

 T (n − 2) if n ≡ 2 (mod 4)
2T (n − 2) if n ≡ 3 (mod 4).


T (n+1)T (n)
Problem 65 [Difficulty Estimate=2.0] Solve the recurrence T (n + 2) = √ ,
T (n+1)2 +T (n)2 +1
where T (1) = 1, T (2) = 5.

Problem 66 ( [85], Problem 6) Let a0 = 0, a1 = 1, and for n ≥ 2, let an = 17an−1 − 70an−2 .

For n > 6, show that the first (most significant) digit of an (when written in base 10) is 3.