Page 528 - Discrete Mathematics and Its Applications

8.1 Applications of Recurrence Relations 507

the order in which these n − k numbers are to be multiplied. Because this final operator can
appear between any two of the n + 1 numbers, it follows that

C n = C 0 C n−1 + C 1 C n−2 + ··· + C n−2 C 1 + C n−1 C 0
n−1

= C k C n−k−1 .
k = 0
Note that the initial conditions are C 0 = 1 and C 1 = 1. ▲

The recurrence relation in Example 5 can be solved using the method of generating func-
tions, which will be discussed in Section 8.4. It can be shown that C n = C(2n, n)/(n + 1) (see
4 n
Exercise 41 in Section 8.4) and that C n ∼ 3/2 √ (see [GrKnPa94]). The sequence {C n } is the
n π
sequence of Catalan numbers, named after Eugène Charles Catalan. This sequence appears
as the solution of many different counting problems besides the one considered here (see the
chapter on Catalan numbers in [MiRo91] or [Ro84a] for details).

Algorithms and Recurrence Relations

Recurrence relations play an important role in many aspects of the study of algorithms and their
complexity. In Section 8.3, we will show how recurrence relations can be used to analyze the
complexity of divide-and-conquer algorithms, such as the merge sort algorithm introduced in
Section 5.4. As we will see in Section 8.3, divide-and-conquer algorithms recursively divide a
problem into a fixed number of non-overlapping subproblems until they become simple enough
to solve directly. We conclude this section by introducing another algorithmic paradigm known
as dynamic programming, which can be used to solve many optimization problems efficiently.
An algorithm follows the dynamic programming paradigm when it recursively breaks down
a problem into simpler overlapping subproblems, and computes the solution using the solutions
of the subproblems. Generally, recurrence relations are used to find the overall solution from
the solutions of the subproblems. Dynamic programming has been used to solve important
problems in such diverse areas as economics, computer vision, speech recognition, artificial
intelligence, computer graphics, and bioinformatics. In this section we will illustrate the use of
dynamic programming by constructing an algorithm for solving a scheduling problem. Before
doing so, we will relate the amusing origin of the name dynamic programming, which was

EUGÈNE CHARLES CATALAN (1814–1894) Eugène Catalan was born in Bruges, then part of France.
His father became a successful architect in Paris while Eugène was a boy. Catalan attended a Parisian school
for design hoping to follow in his father’s footsteps. At 15, he won the job of teaching geometry to his design
school classmates. After graduating, Catalan attended a school for the fine arts, but because of his mathematical
aptitude his instructors recommended that he enter the École Polytechnique. He became a student there, but after
his first year, he was expelled because of his politics. However, he was readmitted, and in 1835, he graduated
and won a position at the Collège de Châlons sur Marne.
In 1838, Catalan returned to Paris where he founded a preparatory school with two other mathemati-
cians, Sturm and Liouville. After teaching there for a short time, he was appointed to a position at the École
Polytechnique. He received his doctorate from the École Polytechnique in 1841, but his political activity in favor of the French
Republic hurt his career prospects. In 1846 Catalan held a position at the Collège de Charlemagne; he was appointed to the Lycée
Saint Louis in 1849. However, when Catalan would not take a required oath of allegiance to the new Emperor Louis-Napoleon
Bonaparte, he lost his job. For 13 years he held no permanent position. Finally, in 1865 he was appointed to a chair of mathematics
at the University of Liège, Belgium, a position he held until his 1884 retirement.
Catalan made many contributions to number theory and to the related subject of continued fractions. He defined what are now
known as the Catalan numbers when he solved the problem of dissecting a polygon into triangles using non-intersecting diagonals.
Catalan is also well known for formulating what was known as the Catalan conjecture. This asserted that 8 and 9 are the only
consecutive powers of integers, a conjecture not solved until 2003. Catalan wrote many textbooks, including several that became
quite popular and appeared in as many as 12 editions. Perhaps this textbook will have a 12th edition someday!