Book of Proof

Home > Other > Book of Proof > Page 24
Book of Proof Page 24

by Richard Hammack


  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.

 

‹ Prev