Book of Proof
Page 24
is a prime factorization of n+1. This competes the proof by strong induction
that every integer greater than 1 has a prime factorization.
Next we use proof by smallest counterexample to prove that the prime
factorization of any n ≥ 2 is unique. If n = 2, then n clearly has only one
prime factorization, namely itself. Assume for the sake of contradiction that
there is an n > 2 that has different prime factorizations n = p1 · p2 · p3 · · · pk
and n = a1 ·a2 ·a3 · · · a `. Assume n is the smallest number with this property.
From n = p1 · p2 · p3 · · · pk, we see that p1 | n, so p1 | (a1 · a2 · a3 · · · a `). By
Proposition 10.1 (page 160), p1 divides one of the primes ai. As ai is prime,
we have p1 = ai. Dividing n = p1 · p2 · p3 · · · pk = a1 · a2 · a3 · · · a ` by p1 = ai
yields
p2 · p3 ··· pk = a1 · a2 · a3 ··· ai−1 · ai+1 ··· a `.
These two factorizations are different, because the two prime factorizations
of n were different. (Remember: the primes p1 and ai are equal, so the
difference appears in the remaining factors, displayed above.) But also the
above number p2 · p3 · · · pk is smaller than n, and this contradicts the fact
that n was the smallest number with two different prime factorizations.
■
Fibonacci Numbers
167
One word of warning about proof by smallest counterexample. In proofs
in other textbooks or in mathematical papers, it often happens that the
writer doesn’t tell you up front that proof by smallest counterexample
is being used. Instead, you will have to read through the proof to glean
from context that this technique is being used. In fact, the same warning
applies to all of our proof techniques. If you continue with mathematics,
you will gradually gain through experience the ability to analyze a proof
and understand exactly what approach is being used when it is not stated
explicitly. Frustrations await you, but do not be discouraged by them.
Frustration is a natural part of anything that’s worth doing.
10.3 Fibonacci Numbers
Leonardo Pisano, now known as Fibonacci, was a mathematician born
around 1175 in what is now Italy. His most significant work was a book
Liber Abaci, which is recognized as a catalyst in medieval Europe’s slow
transition from Roman numbers to the Hindu-Arabic number system. But
he is best known today for a number sequence that he described in his
book and that bears his name. The Fibonacci sequence is
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, . . .
The numbers that appear in this sequence are called Fibonacci numbers.
The first two numbers are 1 and 1, and thereafter any entry is the sum
of the previous two entries. For example 3 + 5 = 8, and 5 + 8 = 13, etc. We
denote the nth term of this sequence as Fn. Thus F1 = 1, F2 = 1, F3 = 2,
F4 = 3, F7 = 13 and so on. Notice that the Fibonacci Sequence is entirely
determined by the rules F1 = 1, F2 = 1, and Fn = Fn−1 + Fn−2.
We introduce Fibonacci’s sequence here partly because it is something
everyone should know about, but also because it is a great source of induc-
tion problems. This sequence, which appears with surprising frequency in
nature, is filled with mysterious patterns and hidden structures. Some of
these structures will be revealed to you in the examples and exercises.
We emphasize that the condition Fn = Fn−1+Fn−2 (or equivalently Fn+1 =
Fn + Fn−1) is the perfect setup for induction. It suggests that we can
determine something about Fn by looking at earlier terms of the sequence.
In using induction to prove something about the Fibonacci sequence, you
should expect to use the equation Fn = Fn−1 + Fn−2 somewhere.
For our first example we will prove that F2
n+1 − Fn+1Fn − F2
n = (−1)n for
any natural number n. For example, if n = 5 we have F2
6 − F6F5 − F 2
5 =
82 − 8 · 5 − 52 = 64 − 40 − 25 = −1 = (−1)5.
168
Mathematical Induction
Proposition
The Fibonacci sequence obeys F2
n+1 − Fn+1Fn − F2
n = (−1)n.
Proof. We will prove this with mathematical induction.
(1) If n = 1 we have F2
n+1 − Fn+1Fn − F2
n = F 2
2 − F2F1 − F 2
1 = 12 − 1 · 1 − 12 = −1 =
(−1)1 = (−1)n, so indeed F2n+1 − Fn+1Fn − F2n = (−1)n is true when n = 1.
(2) Take any integer k ≥ 1. We must show that if F2
−F
= (−1)k
k+1
k+1Fk −F2
k
,
then F2
− F
= (−1)k+1
k+2
k+2Fk+1 − F2
k+1
.
We use direct proof.
Suppose
F2
− F
= (−1)k
k+1
k+1Fk − F2
k
. Now we are going to carefully work out the
expression F2
− F
k+2
k+2Fk+1 − F2
k+1 and show that it really does equal
(−1)k+1. In so doing, we will use the fact that Fk+2 = Fk+1 + Fk.
F2k+2 − Fk+2Fk+1 − F2k+1 = (Fk+1 + Fk)2 −(Fk+1 + Fk)Fk+1 − F2k+1
= F2k+1 + 2Fk+1Fk + F2k − F2k+1 − FkFk+1 − F2k+1
= −F2k+1 + Fk+1Fk + F2k
= −(F2
)
k+1 − Fk+1Fk − F2
k
= −(−1)k
(inductive hypothesis)
= (−1)1(−1)k
= (−1)k+1
Therefore F2
− F
= (−1)k+1
k+2
k+2Fk+1 − F2
k+1
.
It follows by induction that F2
n+1 − Fn+1Fn − F2
n = (−1)n for every n ∈ N.
■
Let’s pause for a moment and think about what the result we just
proved means. Dividing both sides of F2
n+1 − Fn+1Fn − F2
n = (−1)n by F 2
n gives
µ F
¶2
n+1
Fn+1
(−1)n
−
− 1 =
.
Fn
Fn
F2n
For large values of n, the right-hand side is very close to zero, and the
left-hand side is Fn+1/Fn plugged into the polynomial x2 − x − 1. Thus, as
n increases, the ratio Fn+1/Fn approaches a root of x2 − x − 1 = 0. By the
p
1± 5
quadratic formula, the roots of x2 − x − 1 are
2
. As Fn+1/Fn > 1, this ratio
p
1+ 5
must be approaching the positive root
2
. Therefore
p
Fn
1 + 5
lim
+1 =
.
(10.1)
n→∞ Fn
2
p
1+ 5
For a quick spot check, note that F13/F12 ≈ 1.618025, while
2
≈ 1.618033.
Even for the small value n = 12, the numbers m
atch to four decimal places.
Fibonacci Numbers
169
p5
The number Φ = 1+2
is sometimes called the golden ratio, and there
has been much speculation about its occurrence in nature as well as
in classical art and architecture. One theory holds that the Parthenon
and the Great Pyramids of Egypt were designed in accordance with this
number.
But we are here concerned with things that can be proved. We close by
observing how the Fibonacci sequence in many ways resembles a geometric
sequence.
Recall that a geometric sequence with first term a and
common ratio r has the form
a, ar, ar2, ar3, ar4, ar5, ar6, ar7, ar8, . . .
where any term is obtained by multiplying the previous term by r. In
general its nth term is Gn = arn, and Gn+1/Gn = r. Equation (10.1) tells
us that Fn+1/Fn ≈ Φ. Thus even though it is not a geometric sequence,
the Fibonacci sequence tends to behave like a geometric sequence with
common ratio Φ, and the further “out” you go, the higher the resemblance.
Exercises for Chapter 10
Prove the following statements with either induction, strong induction or proof
by smallest counterexample.
n2 + n
1. For every integer n ∈ N, it follows that 1 + 2 + 3 + 4 + ··· + n =
.
2
n(n + 1)(2n + 1)
2. For every integer n ∈ N, it follows that 12 + 22 + 32 + 42 + ··· + n2 =
.
6
n2(n + 1)2
3. For every integer n ∈ N, it follows that 13 + 23 + 33 + 43 + ··· + n3 =
.
4
n(n + 1)(n + 2)
4. If n ∈ N, then 1 · 2 + 2 · 3 + 3 · 4 + 4 · 5 + ··· + n(n + 1) =
.
3
5. If n ∈ N, then 21 + 22 + 23 + ··· + 2n = 2n+1 − 2.
n
6.
X
For every natural number n, it follows that
(8i − 5) = 4n2 − n.
i=1
n(n + 1)(2n + 7)
7. If n ∈ N, then 1 · 3 + 2 · 4 + 3 · 5 + 4 · 6 + ··· + n(n + 2) =
.
6
1
2
3
n
1
8. If n ∈ N, then
+
+
+ · · · +
= 1 −
2!
3!
4!
(n + 1)!
(n + 1)!
9. For any integer n ≥ 0, it follows that 24 | (52n − 1).
10. For any integer n ≥ 0, it follows that 3 | (52n − 1).
11. For any integer n ≥ 0, it follows that 3 | (n3 + 5n + 6).
12. For any integer n ≥ 0, it follows that 9 | (43n + 8).
170
Mathematical Induction
13. For any integer n ≥ 0, it follows that 6 | (n3 − n).
14. Suppose a ∈ Z. Prove that 5 | 2na implies 5 | a for any n ∈ N.
1
1
1
1
1
1
15. If n ∈ N, then
+
+
+
+ · · · +
= 1 −
.
1 · 2
2 · 3
3 · 4
4 · 5
n(n + 1)
n + 1
16. For every natural number n, it follows that 2n + 1 ≤ 3n.
17. Suppose A1, A2,... An are sets in some universal set U, and n ≥ 2. Prove that
A1 ∩ A2 ∩ ··· ∩ An = A1 ∪ A2 ∪ ··· ∪ An.
18. Suppose A1, A2,... An are sets in some universal set U, and n ≥ 2. Prove that
A1 ∪ A2 ∪ ··· ∪ An = A1 ∩ A2 ∩ ··· ∩ An.
1
1
1
1
1
19. Prove that
+
+
+ · · · +
≤ 2 − .
1
4
9
n2
n
20. Prove that (1 + 2 + 3 + ··· + n)2 = 13 + 23 + 33 + ··· + n3 for every n ∈ N.
1
1
1
1
1
1
1
n
21. If n ∈ N, then
+
+
+
+
+ · · · +
+
≥ 1 + .
1
2
3
4
5
2n − 1
2n
2
(Note: This problem asserts that the sum of the first 2n terms of the harmonic
series is at least 1 + n/2. It thus implies that the harmonic series diverges.)
µ
1 ¶ µ
1 ¶ µ
1 ¶ µ
1 ¶
µ
1 ¶
1
1
22. If n ∈ N, then 1 −
1 −
1 −
1 −
· · · 1 −
≥
+
2
4
8
16
2n
4
2n+1 .
23. Use mathematical induction to prove the binomial theorem (Theorem 3.1 on
page 80). You may find that you need Equation (3.2) on page 78.
n
24.
X
¢
Prove that
k ¡ nk = n2n−1 for each natural number n.
k=1
25. Concerning the Fibonacci sequence, prove that F1+F2+F3+F4+...+Fn = Fn+2−1.
n
26.
X
Concerning the Fibonacci sequence, prove that
F2k = FnFn+1.
k=1
27. Concerning the Fibonacci sequence, prove that F1 +F3 +F5 +F7 +...+F2n−1 = F2n.
28. Concerning the Fibonacci sequence, prove that F2 + F4 + F6 + F8 + ... + F2n =
F2n+1 − 1.
29. In this problem n ∈ N and Fn is the nth Fibonacci number. Prove that
¡ n ¢
¢
¢
¢
¢
0 + ¡ n−1
1
+ ¡ n−2
2
+ ¡ n−3
3
+ · · · + ¡ 0n = Fn+1.
¡ 6 ¢
¢
¢
¢
¢
¢
¢
(For example, 0 + ¡ 51 + ¡ 42 + ¡ 33 + ¡ 24 + ¡ 15 + ¡ 06 = 1+5+6+1+0+0+0 = 13 = F6+1.)
30. Here Fn is the nth Fibonacci number. Prove that
p
p
³ 1+ 5 ń
³ 1− 5 ń
2
−
2
Fn =
p
.
5
n
31.
X ¡ k ¢
¢
Prove that
r
= ¡ n+1
r+1 , where 1 ≤ r ≤ n.
k=0
32. Prove that the number of n-digit binary numbers that have no consecutive
1’s is the Fibonacci number Fn+2. For example, for n = 2 there are three such
Fibonacci Numbers
171
numbers (00, 01, and 10), and 3 = F2+2 = F4. Also, for n = 3 there are five such
numbers (000, 001, 010, 100, 101), and 5 = F3+2 = F5.
33. Suppose n (infinitely long) straight lines lie on a plane in such a way that no
two of the lines are parallel, and no three of the lines intersect at a single
n2+n+2
point. Show that this arrangement divides the plane into
2
regions.
3n+1 − 3
34. Prove that 31 + 32 + 33 + 34 + ··· + 3n =
for every n ∈ N.
2
35.
¡n¢
Prove that if n, k ∈ N, and n is even and k is odd, then k is even.
36. Prove that if n = 2k −1 for some k ∈ N, then every entry in the nth row of Pascal’s
triangle is odd.
The remaining odd-numbered exercises below are not solved in the back of the
book.
n
37.
P
¢
¢
¢
Prove that if m, n ∈ N, then
k¡m+k
m
= n¡m+n+1
m
− ¡m+n+1
+1
m+2
.
k=0
38.
¡n¢2
¢2
¢2
¢2
¢
Prove that if n is a positive integer, then 0 + ¡n1 + ¡n2 + · · · + ¡nn
= ¡2n
n .
39.
¡n+0¢
¢
¢
¢
¢
Prove that if n is a positive integer, then
0
+ ¡n+1
1
+ ¡n+2
2
+ · · · + ¡n+k
k
= ¡n+k+1
k
.
p
40.
P ¡m¢¡
n ¢
¢
Prove that
k
p
= ¡m+n
−k
p
for positive integers m, n and p.
k=0
m
41.
P ¡m¢¡
n ¢
¢
Prove that
k
p
= ¡m+n
+k
m+p for positive integers m, n and p.
k=0
Part IV
Relations, Functions and
Cardinality
CHAPTER
11
Relations
n mathematics there are endless ways that two entities can be related
I to each other. Consider the following mathematical statements.
5 < 10
5 ≤ 5
6 = 30
5
5
| 80
7 > 4
x 6= y
8 - 3
p
a ≡ b ( mod n)
6 ∈ Z
X ⊆ Y
π ≈ 3.14
0 ≥ −1
2 ∉ Z
Z 6⊆ N
In each case two entities appear on either side of a symbol, and we
interpret the symbol as expressing some relationship between the two
entities. Symbols such as <, ≤, =, |, -, ≥, >, ∈ and ⊂, etc., are called relations
because they convey relationships among things.
Relations are significant. In fact, you would have to admit that there
would be precious little left of mathematics if we took away all the relations.
Therefore it is important to have a firm understanding of them, and this
chapter is intended to develop that understanding.