Page 128 - Discrete Mathematics and Its Applications

1.8 Proof Methods and Strategy 107

proof, requiring hundreds of pages of advanced mathematics, was not found until the 1990s,
when Andrew Wiles used recently developed ideas from a sophisticated area of number theory
called the theory of elliptic curves to prove Fermat’s last theorem. Wiles’s quest to find a
proof of Fermat’s last theorem using this powerful theory, described in a program in the Nova
series on public television, took close to ten years! Moreover, his proof was based on major
contributions of many mathematicians. (The interested reader should consult [Ro10] for more
information about Fermat’s last theorem and for additional references concerning this problem
and its resolution.)
We now state an open problem that is simple to describe, but that seems quite difficult to
resolve.

EXAMPLE 23 The 3x + 1 Conjecture Let T be the transformation that sends an even integer x to x/2 and
an odd integer x to 3x + 1. A famous conjecture, sometimes known as the 3x + 1 conjec-
ture, states that for all positive integers x, when we repeatedly apply the transformation T ,
we will eventually reach the integer 1. For example, starting with x = 13, we find T(13) =
3 · 13 + 1 = 40, T(40) = 40/2 = 20, T(20) = 20/2 = 10, T(10) = 10/2 = 5, T(5) =
3 · 5 + 1 = 16, T(16) = 8, T(8) = 4, T(4) = 2, and T(2) = 1. The 3x + 1 conjecture has
13
been verified using computers for all integers x up to 5.6 · 10 .
The 3x + 1 conjecture has an interesting history and has attracted the attention of mathe-
maticians since the 1950s. The conjecture has been raised many times and goes by many other
names, including the Collatz problem, Hasse’s algorithm, Ulam’s problem, the Syracuse prob-
lem, and Kakutani’s problem. Many mathematicians have been diverted from their work to spend
time attacking this conjecture. This led to the joke that this problem was part of a conspiracy
Watch out! Working on
the 3x + 1 problem can to slow down American mathematical research. See the article by Jeffrey Lagarias [La10] for a
be addictive. fascinating discussion of this problem and the results that have been found by mathematicians
attacking it. ▲

In Chapter 4 we will describe additional open questions about prime numbers. Students
already familiar with the basic notions about primes might want to explore Section 4.3, where
these open questions are discussed. We will mention other important open questions throughout
the book.

Additional Proof Methods

In this chapter we introduced the basic methods used in proofs.We also described how to leverage
these methods to prove a variety of results. We will use these proof methods in all subsequent
chapters. In particular, we will use them in Chapters 2, 3, and 4 to prove results about sets,
Build up your arsenal of
proof methods as you functions, algorithms, and number theory and in Chapters 9, 10, and 11 to prove results in graph
work through this book. theory. Among the theorems we will prove is the famous halting theorem which states that there
is a problem that cannot be solved using any procedure. However, there are many important
proof methods besides those we have covered. We will introduce some of these methods later
in this book. In particular, in Section 5.1 we will discuss mathematical induction, which is an
extremely useful method for proving statements of the form ∀nP(n), where the domain consists
of all positive integers. In Section 5.3 we will introduce structural induction, which can be used
to prove results about recursively defined sets. We will use the Cantor diagonalization method,
which can be used to prove results about the size of infinite sets, in Section 2.5. In Chapter 6
we will introduce the notion of combinatorial proofs, which can be used to prove results by
counting arguments. The reader should note that entire books have been devoted to the activities
discussed in this section, including many excellent works by George Pólya ([Po61], [Po71],
[Po90]).
Finally, note that we have not given a procedure that can be used for proving theorems in
mathematics. It is a deep theorem of mathematical logic that there is no such procedure.