Section 2.1 Proof Techniques
107
eXAMPLe 13
A standard 64-square checkerboard is arranged in 8 rows of 8 squares each. Adjacent squares are alternating colors of red and black. A set of 32 1 × 2 tiles, each
covering 2 squares, will cover the board completely (4 tiles per row, 8 rows). Prove
that if the squares at diagonally opposite corners of the checkerboard are removed,
the remaining board cannot be covered with 31 tiles.
The hard way to prove this result is to try all possibilities with 31 tiles and see
that they all fail. The clever observation is to note that opposing corners are the
same color, so the checkerboard with the corners removed has two less squares of
one color than of the other. Each tile covers one square of each color, so any set
of tiles must cover an equal number of squares of each color and cannot cover the
board with the corners removed.
S e c t i o n 2 . 1 review
tecHniQueS
• Look for a counterexample.
• Construct direct proofs, proofs by contraposition,
and proofs by contradiction.
MAin iDeAS
• Inductive reasoning is used to formulate a conjecture based on experience. Deductive reasoning
is used either to refute a conjecture by finding a
counterexample or to prove a conjecture.
• In proving a conjecture about some subject, facts
about that subject can be used.
• Under the right circumstances, proof by contraposition or contradiction may work better than a
direct proof.
W
eXeRciSeS 2.1
1. Write the contrapositive of each statement in Exercise 5 of Section 1.1.
2. Write the converse of each statement in Exercise 5 of Section 1.1.
Common Definitions
Many of the examples in this section and many of the exercises that follow involve
elementary number theory, that is, results about integers. It’s useful to work in
number theory when first starting to construct proofs because many properties of
integers, such as what it means to be an even number, are already familiar. The
following definitions may be helpful in working some of these exercises.
• A perfect square is an integer n such that n = k
2
for some integer k.
• A prime number is an integer n > 1 such that n is not divisible by any
integers other than 1 and n.
• A composite number n is a nonprime integer; that is, n = ab where a and
b are integers with 1 < a < n and 1 < b < n.
• For two numbers x and y, x < y means y − x > 0.
• For two integers n and m, n divides m, n 0 m, means that m is divisible by
n—that is, m = k(n) for some integer k.
• The absolute value of a number x, 0 x 0 , is x if x ≥ 0 and is −x if x < 0.
107
eXAMPLe 13
A standard 64-square checkerboard is arranged in 8 rows of 8 squares each. Adjacent squares are alternating colors of red and black. A set of 32 1 × 2 tiles, each
covering 2 squares, will cover the board completely (4 tiles per row, 8 rows). Prove
that if the squares at diagonally opposite corners of the checkerboard are removed,
the remaining board cannot be covered with 31 tiles.
The hard way to prove this result is to try all possibilities with 31 tiles and see
that they all fail. The clever observation is to note that opposing corners are the
same color, so the checkerboard with the corners removed has two less squares of
one color than of the other. Each tile covers one square of each color, so any set
of tiles must cover an equal number of squares of each color and cannot cover the
board with the corners removed.
S e c t i o n 2 . 1 review
tecHniQueS
• Look for a counterexample.
• Construct direct proofs, proofs by contraposition,
and proofs by contradiction.
MAin iDeAS
• Inductive reasoning is used to formulate a conjecture based on experience. Deductive reasoning
is used either to refute a conjecture by finding a
counterexample or to prove a conjecture.
• In proving a conjecture about some subject, facts
about that subject can be used.
• Under the right circumstances, proof by contraposition or contradiction may work better than a
direct proof.
W
eXeRciSeS 2.1
1. Write the contrapositive of each statement in Exercise 5 of Section 1.1.
2. Write the converse of each statement in Exercise 5 of Section 1.1.
Common Definitions
Many of the examples in this section and many of the exercises that follow involve
elementary number theory, that is, results about integers. It’s useful to work in
number theory when first starting to construct proofs because many properties of
integers, such as what it means to be an even number, are already familiar. The
following definitions may be helpful in working some of these exercises.
• A perfect square is an integer n such that n = k
2
for some integer k.
• A prime number is an integer n > 1 such that n is not divisible by any
integers other than 1 and n.
• A composite number n is a nonprime integer; that is, n = ab where a and
b are integers with 1 < a < n and 1 < b < n.
• For two numbers x and y, x < y means y − x > 0.
• For two integers n and m, n divides m, n 0 m, means that m is divisible by
n—that is, m = k(n) for some integer k.
• The absolute value of a number x, 0 x 0 , is x if x ≥ 0 and is −x if x < 0.