110
Proofs, Induction, and Number Theory
62. If n, m, and p are integers and n 0 mp, then n 0 m or n 0 p.
63. For every prime number n, n + 4 is prime.
64. For every positive integer n, n
2
+ n + 3 is not prime.
65. For n a positive integer, n > 2, n
2
− 1 is not prime.
66. For every positive integer n, 2
n
+ 1 is prime.
67. For every positive integer n, n
2
+ n + 1 is prime.
68. For n an even integer, n > 2, 2
n
− 1 is not prime.
69. The sum of two rational numbers is rational.
70. The product of two rational numbers is rational.
71. The product of two irrational numbers is irrational.
72. The sum of a rational number and an irrational number is irrational.
For Exercises 73–75, use the following facts from geometry and the accompanying figure.
• The interior angles of a triangle sum to 180°.
• Vertical angles (opposite angles formed when two lines intersect) are the same size.
• A straight angle is 180°.
• A right angle is 90°.
1
2
3
4
6
5
73. Prove that the measure of angle 5 plus the measure of angle 3 is 90°.
74. Prove that the measure of angle 4 is the sum of the measures of angles 1 and 2.
75. If angle 1 and angle 5 are the same size, then angle 2 is a right angle.
76. Prove that the sum of the integers from 1 through 100 is 5050. (Hint: Instead of actually adding all the
numbers, try to make the same clever observation that the German mathematician Karl Friederick Gauss
[1777–1855] made as a schoolchild: Group the numbers into pairs, using 1 and 100, 2 and 99, etc.)
S e c t i o n 2 . 2 induCTion
First Principle of Induction
There is one final proof technique especially useful in computer science. To
illustrate how the technique works, imagine that you are climbing an infinitely
high ladder. How do you know whether you will be able to reach an arbitrarily
high rung? Suppose we make the following two assertions about your climbing
abilities:
1. You can reach the first rung.
2. Once you get to a rung, you can always climb to the next one up. (Notice
that this assertion is an implication.)
Proofs, Induction, and Number Theory
62. If n, m, and p are integers and n 0 mp, then n 0 m or n 0 p.
63. For every prime number n, n + 4 is prime.
64. For every positive integer n, n
2
+ n + 3 is not prime.
65. For n a positive integer, n > 2, n
2
− 1 is not prime.
66. For every positive integer n, 2
n
+ 1 is prime.
67. For every positive integer n, n
2
+ n + 1 is prime.
68. For n an even integer, n > 2, 2
n
− 1 is not prime.
69. The sum of two rational numbers is rational.
70. The product of two rational numbers is rational.
71. The product of two irrational numbers is irrational.
72. The sum of a rational number and an irrational number is irrational.
For Exercises 73–75, use the following facts from geometry and the accompanying figure.
• The interior angles of a triangle sum to 180°.
• Vertical angles (opposite angles formed when two lines intersect) are the same size.
• A straight angle is 180°.
• A right angle is 90°.
1
2
3
4
6
5
73. Prove that the measure of angle 5 plus the measure of angle 3 is 90°.
74. Prove that the measure of angle 4 is the sum of the measures of angles 1 and 2.
75. If angle 1 and angle 5 are the same size, then angle 2 is a right angle.
76. Prove that the sum of the integers from 1 through 100 is 5050. (Hint: Instead of actually adding all the
numbers, try to make the same clever observation that the German mathematician Karl Friederick Gauss
[1777–1855] made as a schoolchild: Group the numbers into pairs, using 1 and 100, 2 and 99, etc.)
S e c t i o n 2 . 2 induCTion
First Principle of Induction
There is one final proof technique especially useful in computer science. To
illustrate how the technique works, imagine that you are climbing an infinitely
high ladder. How do you know whether you will be able to reach an arbitrarily
high rung? Suppose we make the following two assertions about your climbing
abilities:
1. You can reach the first rung.
2. Once you get to a rung, you can always climb to the next one up. (Notice
that this assertion is an implication.)