Topic 3 - tehrhte PDF

Preview

Summary

MATH1081 Discrete Mathematics F and D D Topic 3 Proof, Induction and Symbolic Logic 3 Mathematical Induction The Principle of Mathematical Induction is a technique for proving statements concerning the natural numbers N 1, 2, 3, 4, . . and other sets like Z n n0 where n0 is some given integer. Induc...

Description

MATH1081 Discrete Mathematics

F.Kuo and D.Angell / D.Trenerry

Topic 3 Proof, Induction and Symbolic Logic 3.2 Mathematical Induction The Principle of Mathematical Induction is a technique for proving statements concerning the natural numbers N = {0, 1, 2, 3, 4, . . .} and other sets like {n ∈ Z | n ≥ n0 } where n0 is some given integer. Induction is poorly taught or understood at High School. We are going to do it in a formal way which hopefully will help you better understand induction and better set out an induction proof. In tests and exams, you should use our formal approach. The term “proposition” is commonly wrongly used in induction arguments, where “predicate” is the correct term – so we will use the term predicate.

1

A formal induction proof takes the following form. To prove for a predicate P (n) that “P (n) is true for all n ∈ N”: Basis step: show that “P (0) is true”. Induction step: show that “for all k ∈ N, if P (k) is true then P (k + 1) is true” (or “the truth of P (k) implies the truth of P (k + 1)”) via: Let k ∈ N. (Note that k is arbitrary, but fixed once chosen.) Suppose that P (k) is true. (This is called the induction hypothesis .) .. . Hence P (k + 1) is also true. The proof then ends with a conclusion : “Hence by induction, P (n) is true for all n ∈ N.”

2

For an induction on {n ∈ Z | n ≥ n0 }, simply change the basis step to “show P (n0 ) is true” and ensure k ≥ n0 in the induction step.

The following is a High School intuitive understanding which is NOT a proof: The base step leads to P (0) is true The induction step leads to P (0) implies P (1) P (1) implies P (2) P (2) implies P (3) etc. Combining both steps leads to P (0) P (1) P (2) P (3) etc.

is is is is

true true true true

Note however, that this is NOT A PROOF that induction works. 3

The Principle of Induction is actually an Axiom of Mathematics and therefore CANNOT be proved. It has to be taken as fact. NEVER try to explain it using the approach above. Here is one form of the Peano Axioms for N that form the basis of Mathematics: 0 ∈ N.

There is an injective function f : N → N such that 0 6∈ f (N). If, whenever S ⊆ N is such that

0 ∈ S and whenever x ∈ S, then f (x) ∈ S ,

then S = N. This function f is called the successor function. Think f (n) = n + 1. The first two Axioms say evey natural number except 0 is the successor of a natural number. Axiom 3 says that the principle of induction holds. The Peano Axions will NOT BE EXAMINED. 4

Example. Prove by induction that n3 +2n is a multiple of 3 for all natural numbers n. A formal induction proof... (you may treat the green part as a template) Proof. Let P (n) be the predicate “ n3 + 2n

is a multiple of 3

”.

We want to prove that P (n) is true for all n ∈ N. Basis step: For n = 0, we have 03 + 2 × 0 = 0 = 3 × 0, which is a multiple of 3. Hence P (0) is true. Induction step: Suppose that k ∈ N. (This k is arbitrary, but fixed once chosen.) Suppose that (for this k), P (k) is true. Then k 3 + 2k = 3m for some integer m. 5

(induction hypothesis)

We want to deduce that that P (k + 1) is true, that is, (k + 1)3 + 2(k + 1) is a multiple of 3. We have (k + 1)3 + 2(k + 1) = k 3 + 3k 2 + 3k + 1 + 2k + 2 = (k 3 + 2k) + 3k 2 + 3k + 3 by the induction hypothesis = 3m + 3k 2 + 3k + 3 = 3(m + k 2 + k + 1), which is a multiple of 3. Hence we have deduced that P (k + 1) is true. Thus we have shown that for all k ∈ N, if P (k) is true then P (k + 1) is true. Conclusion: Hence by induction, P (n) is true for all n ∈ N. 6

✷

Note that this particular problem would be far quicker done using a proof by cases. Note the difference between our formal way of writing the induction step: “For any k ∈ N, if P (k) is true then P (k + 1) is true.” and some other ways of writing the induction step that are commonly used by teachers and mathematicians, but are not quite right ..... “Assume P (n) is true, then we prove that P (n + 1) is true” – this seems to assume what we have to prove and does not quantify n. “We prove that if P (k) is true, then P (k + 1) is true” – this does not properly quantify k . “If P (n) is true for some particular value of n then we show P (n + 1) is true” – using the words “some particular” makes this sound like “there is some particular n such that if P (n) it true then P (n + 1) is true”, and so this has the wrong quantifier. (Epp uses this in places.) The intention here seems to be that k is “an arbitrary then particular value” (rather than “some particular value”) of n. 7

Some other correct ways of stating the induction step: “For any n ∈ N, if P (n) is true then P (n + 1) is true”. Note, however, using k instead of n psychologically separates the induction step from what you are trying to prove, so is a useful approach. “Whenever P (k) is true for some arbitrary k ∈ N, then it follows that P (k + 1) is true.” “Suppose k is a value in N for which P (k) is true, then we prove that P (k + 1) is true” – this is OK but not as formal as our way. An informal approach is to say “For an arbitrary k ∈ N, suppose the result holds for n = k, then we prove it holds for n = k + 1”, which does not formally identify the predicate. You should use our formal approach in MATH1081.

8

Example. Prove by induction that the sum of the squares of the first n positive integers 1 12 + 22 + · · · + n2 = n(n + 1)(2n + 1). 6 Induction can start at integers other than 0. Proof. Let P (n) be the predicate “12 + 22 + · · · + n2 = 61n(n + 1)(2n + 1)”. Basis step: For n = 1, we have LHS = 12 = 1 =

1 × 1 × (1 + 1) × (2 × 1 + 1) = RHS. 6

Hence P (1) is true. Induction step: Let k ∈ N with k ≥ 1. Suppose that P (k) is true, that is, 1 12 + 22 + · · · + k 2 = k(k + 1)(2k + 1). (induction hypothesis) 6 9

We want to deduce that P (k + 1) is true, that is, 1 12 + 22 + · · · + k 2 + (k + 1)2 = (k + 1)((k + 1) + 1)(2(k + 1) + 1). 6 We have LHS = (12 + 22 + · · · + k 2 ) + (k + 1)2 1 by the induction hypothesis = k(k + 1)(2k + 1) + (k + 1)2 6 1 = (k + 1)[k(2k + 1) + 6(k + 1)] 6 1 = (k + 1)[2k 2 + 7k + 6] 6 1 = (k + 1)(k + 2)(2k + 3) 6 and we have deduced that P (k + 1) is true. = RHS, Thus we have shown that for all k ∈ N with k ≥ 1, P (k) implies P (k + 1). Conclusion: Hence by induction, P (n) is true for all positive integers n. 10

✷

What is wrong with the following as an attempt at part of the previous proof? “ By the induction hypothesis, we have 1 12 + 22 + · · · + k 2 = k(k + 1)(2k + 1). 6 Replace k by k + 1. Therefore 1 12 + 22 + · · · + (k + 1)2 = (k + 1)(k + 2)(2k + 3), 6 which completes the induction step. ” Answer. The assumption in the induction step is that for some arbitrary, but then fixed k ∈ N with k ≥ 1, 1 12 + 22 + · · · + k 2 = k(k + 1)(2k + 1). 6 Therefore it is not valid to substitute any other value of k (like k + 1) into this equation. 11

Example. Show that 16 | 5n − 4n − 1 for all n ≥ 1. Proof. Let P (n) be the predicate “16 | 5n − 4n − 1”.

Basis: We note that P (1) is true since 51 − 4 × 1 − 1 = 0 is divisible by 16.

Induction: Let k ∈ N with k ≥ 1. Assume that P (k) is true, so that 16 | 5k − 4k − 1. Then there is an integer m with 5k − 4k − 1 = 16m. Now 5k+1 − 4(k + 1) − 1 = 5(5k ) − 4k − 5 = 5(16m + 4k + 1) − 4k − 5 by the induction hypothesis = 5 × 16m + 16k and this is divisible by 16, so P (k + 1) is true. We have proved that for all k ∈ N with k ≥ 1, P (k) implies P (k + 1).

Conclusion: By induction 16 | 5n − 4n − 1 for all n ≥ 1. 12

✷

Example. (Generalized Bezout Identity) Let n ≥ 2 be an integer. For any n integers a1 , a2 , · · · , an having no common factor, there exist integers x1 , x2 , · · · , xn such that a1 x1 + a2 x2 + · · · + an xn = 1. Proof. Let P (n) be the predicate “For any n integers a1 , a2 , · · · , an having no common factor, there exist integers x1 , x2 , · · · , xn such that a1 x1 + a2 x2 + · · · + an xn = 1.”

Basis: Now P (2) is true, and was proved in section 2 of this course. Induction: Let k ∈ N with k ≥ 2. Now assume that P (k) is true, and let a1 , · · · , ak , ak+1 be integers with no common factor. We must deduce that a1 x1 + · · · + ak xk + ak+1 xk+1 = 1 13

for some integers x1 , · · · , xk , xk+1 .

(1)

Let g be the greatest common divisor of a1 , · · · , ak . a1 ak are k integers having no common factor, Then ,··· , g and so gby the induction assumption there exist integers y1 , · · · , yk such that     a1 ak yk = 1. (2) y1 + · · · + g g Moreover, g and ak+1 have no common factor (if they did, it would be a common factor of a1 , · · · , ak , ak+1 ). So by the Basis case we have gz + ak+1 zk+1 = 1

(3)

for some integers z and zk+1 . Multiplying equation (2) by g and substituting into (3) gives (a1 y1 + · · · + ak yk )z + ak+1 zk+1 = 1.

14

Finally choosing x1 = y1 z, · · · , xk = yk z and xk+1 = zk+1 gives a solution of equation (1), and we have deduced that P (k + 1) is true. Hence we have shown that for all k ∈ N with k ≥ 2, P (k) implies P (k + 1). Conclusion By induction, P (n) is true for all n ≥ 2. ✷ Here we have proved by induction a doubly quantified statement of the form “for all . . . there exists . . . ”. In this case the connection between the property for k and for k + 1 is that we need to add one more term on the left hand side. This proof is a bit unusual in that it uses the Basis case to prove the Induction step. As we have already seen a number of times, the “some” part of the statement was proved by producing a specific example of the numbers required. The argument also makes use of a short proof by contradiction (if they did, then . . . ). 15

Exercise. Prove by induction that n3 ≤ 3n for all natural numbers n ≥ 3. Proof. (We will use an informal induction proof for a change) Basis: Clearly the result holds for n = 3. Induction: Suppose k ∈ N and k ≥ 3, and suppose that the result holds for n = k . Then we have 3

(k + 1) = ≤ = ≤

(k + 1)3 k × k3 (k + 1)3 k 3 × k3  3 1 3k × 1 + k 3k × 3 3

= 3k+1 .

16

by the induction hypothesis

since (1 + k1 )3 ≤ (1 + 13 )3 ≤ 3 for k ≥ 3

Thus we have shown that the result also holds for n = k + 1. Conclusion: Hence by induction, the result holds for all natural numbers n ≥ 3.

✷

Note that informal induction proofs are often used in mathematics, but they tend to hide exactly what is being proved, which here is (for Universe N), (P (3) is true) and (∀k ≥ 3, P (k) implies P (k + 1)), hence by induction (∀n ≥ 3, P (n) is true).

Avoid informal induction proofs in your Tests and Exam.

17

Strong Induction or Extended Induction Suppose that we are given some n0 ∈ Z and m ∈ N, then a strong induction proof consists of two steps: Basis step: show that P (n0 ), P (n0 + 1), · · · , P (n0 + m) are true. Induction step: show that for all k ∈ N with k ≥ n0 + m, the truth of all of P (n0 ), P (n0 + 1), · · · , P (k) implies the truth of P (k + 1) via: Let k ∈ N with k ≥ n0 + m. Suppose that all of P (n0 ), P (n0 + 1), . . . , P (k) are true. (This is called the induction hypothesis.) .. . Hence P (k + 1) is also true. The proof then ends with a conclusion : “Hence by (strong) induction, P (n) is true for all n ∈ N.” 18

Example. Suppose the sequence {un } has the properties u0 = 2, u1 = 6,

un+2 = 6un+1 − 8un for all n ≥ 0.

Then for all n ≥ 0 we have un = 4n + 2n . Proof. Let P (n) be the predicate “ un = 4n + 2n ”. Basis: Letting n = 0 and n = 1 we get 2 = 1 + 1 and 6 = 4 + 2 respectively; so both P (0) and P (1) are true. Induction: Let k ∈ N. Assume that P (k) and P (k + 1) are both true, that is, uk = 4k + 2k and uk+1 = 4k+1 + 2k+1 . We must deduce that

uk+2 = 4k+2 + 2k+2 .

Now we are given that 19

LHS = uk+2 = 6uk+1 − 8uk

and substituting the assumed equalities for k and k + 1 gives, LHS = 6 × (4k+1 + 2k+1 ) − 8 × (4k + 2k ) = (6 × 4 − 8)4k + (6 × 2 − 8)2k = 42 × 4k + 22 × 2k = RHS.

This means that P (k + 2) is true. Hence we have shown that for all k ∈ N, the truth of both P (k) and P (k + 1) implies the truth of P (k + 2). Conclusion By (strong) induction, the formula is true for all n ≥ 0.

✷

Note that we varied the induction slightly to get P (k + 2) from P (k) and P (k + 1) as the flow of the proof is better. Here we used n0 = 0, m = 1 in the strong induction and only needed to assume two of the previous P ( ... ) instead of all of them. 20

Exercise. The Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, . . . are defined by the recurrence relation F0 = 0,

F1 = 1,

and Fn = Fn−1 + Fn−2

for all n ≥ 2.

Prove by induction that Fn =

√1 5

h

√ n 1+ 5 2

−



√ n i 1− 5 2

for all n ∈ N.

We will leave this as an exercise – see Problem Sheet 3 Question 55.

Here we also use n0 = 0, m = 1 and only two of the previous cases. In the next example we will use n0 = 2, m = 0 and have to assume all the previous cases even though we only use two of them – as we do not know which two we will use. 21

Example. Prove that any integer n ≥ 2 can be written as a product of primes. Proof. (Informal) Basis: Since 2 is a product of one prime, the result is true for n = 2. Induction: Suppose k is an integer and k ≥ 2. Suppose that the result is true for all n = 2, 3, . . . , k. We want to prove that the result is also true for n = k + 1, that is, we want to show that k + 1 can be written as a product of primes. There are two cases to consider: either k + 1 is prime or k + 1 is composite. If k + 1 is prime, then it is a product of one prime. If k + 1 is composite, then we can write k + 1 = ab for some integers 2 ≤ a, b ≤ k . By the induction hypothesis, both a and b can be written as products of primes, and thus k + 1 = ab can be written as a product of primes. Hence k + 1 can be written as the product of primes. Conclusion: Hence by (strong) induction, we conclude that any integer greater than or equal to 2 can be written as a product of primes. ✷ 22

Exercise. Prove by induction that postage of 24 cents or more can be achieved by using 5-cent stamps and 7-cent stamps. Proof. (Informal) Basis: We have 24c = 2 × 5c + 2 × 7c 25c = 5 × 5c 26c = 1 × 5c + 3 × 7c 27c = 4 × 5c + 1 × 7c 28c = 4 × 7c Hence, postage of 24c, 25c, 26c, 27c, 28c can be achieved by using 5c and 7c stamps.

23

Induction: Suppose that k is an integer and k ≥ 28. Suppose we have shown how to construct postage of every value from 24 cents up to k cents. We need to show how to construct postage of k + 1 cents. We can write k + 1 = (k + 1) − 5 + 5 = (k − 4) + 5. Since k ≥ 28, we have k − 4 ≥ 24. By the induction hypothesis, we can construct postage of k −4 cents using m 5-cent stamps and n 7-cent stamps for some natural numbers m and n, that is, k − 4 = 5m + 7n. Thus k + 1 = (5m + 7n) + 5 = 5(m + 1) + 7n, which means that we can construct postage of k + 1 stamps using m + 1 5-cent stamps and n 7-cent stamps. Conclusion: Hence by (strong) induction, postage of 24 cents or more can be achieved by using 5-cent stamps and 7-cent stamps. ✷ 24

Here we used n0 = 24, m = 4 in the strong induction, and used the last five of P (24), · · · , P (k) to get P (k + 1). Note that we have also proved that for all natural numbers n ≥ 24 5x + 7y = n has a solution with x, y ∈ N. You might like to reflect on conditions on a, b, n0 such that: for every n ≥ n0 ax + by = n has solutions with x, y ∈ N.

25

Example. Let π = 3.14159 · · · = d0 .d1 d2 d3 · · ·

(di are the digits of π)

(and define a sequence {un } by u0 = 1 and un+1 = d0 un + d1 un−1 + · · · + dn u0 for n ≥ 0. Then for n ≥ 1

un ≤ 9 × 10n−1 .

Proof. Let P (n) be the predicate “ un ≤ 9 × 10n−1 ” . Basis: Now P (1) is true since u1 = 3 ≤ 9.

26

Induction: Let k ∈ N with k ≥ 1 Assume that P (1), P (2), · · · , P (k) are true. We shall deduce that P (k + 1) is true, that is uk+1 ≤ 9 × 10k .

Now LHS = d0 uk + d1 uk−1 + · · · + dk−1 u1 + dk u0 ≤ 9 × (uk + uk−1 + · · · + u1 + u0 )

≤ 9 × (9 × 10k−1 + 9 × 10k−2 + · · · + 9 + 1)

by the induction hypothesis. Hence LHS ≤ 9 × (99 · · 99} +1) = 9 × 10k , | ·{z k digits which is what we had to show and so P (k + 1) is true. Hence we have deduced that for any k ∈ N with k ≥ 1, that the truth of all of P (1), P (2), · · · , P (k) implies the truth of P (k + 1). Conclusion: By strong induction P (n) is true for all n ≥ 1.

✷

Here we had n0 = 1, m = 0 and had to use ALL of P (1), · · · , P (k) to get P (k + 1). What role, if any, did π have in the proof? 27

Some different kinds of induction problems Exercise. Prove by induction that for any positive integer n ≥ 3, the sum of the interior angles of a convex n-gon is 180(n − 2) degrees. IDEA: 1. The sum of the interior angles of a triangle is 180 degrees. 2. Any convex (k + 1)-gon can be split into a convex k-gon and a triangle.

28

Exercise. Let n be a positive integer. Prove by induction that any 2n × 2n checkerboard with one corner square removed can be tiled using L-shaped pieces formed by three 1 × 1 squares. (These pieces are called L-triominos or right triominos .) The L-triominoes look like this:

IDEA: Four 2k × 2k boards, and one L-triomino.

29

Exercise. Large dots are drawn on the circumference of a circle and lines are drawn joining the dots in pairs so that every dot is joined to every other dot by a line. Prove by induction that for every positive integer n ≥ 2, if n dots are drawn then they will be joined in pairs by 21 n(n − 1) lines. IDEA: Add an additional dot to a diagram with k dots. This additional dot can be joined to each of the existing k dots, giving a further k lines.

Exercise. Straight lines are drawn right across an A4 sheet of paper in such a way that each pair of lines intersect and no three or more lines intersect at the same point. Prove by induction that when n such lines are drawn, they divide the sheet of paper into 21 (n2 + n + 2) regions. IDEA: Add an additional line to a paper with k such lines. This additional line divides k regions into 2, thus creating an additional k regions. 30

The Well-ordering Principle for the natural numbers says: “Every non-empty subset S of N contains a least element.” This is an alternate Axiom to the Principle of Induction. In fact it is not too hard to show by suitably setting up predicates or subsets that: The “Principle of Induction”, the “Strong Principle of Induction” and the “Well-ordering Principle for the natural numbers” are logically equivalent to one another, meaning: assume one of them and you can deduce the other two. Moreover, they are all equivalent to “Fermat’s Method of Descent”, which was the form in which induction first appeared in the 17th century. Fermat’s Method of Descent is obtained from induction using the ideas of contrapositive/contradiction: To show that P (n) is true for all n ≥ n0 , show for all n ≥ n0 + 1, P (n) false implies P (n − 1) is false but P (n0 ) is true.

31

Example. (Hard) (Historically one of the earliest uses of “induction”) Show that any natural number of the form 4n (8m + 7) for some n, m ∈ N cannot be written as the sum of three squares of integers. (Call this P (n).) Proof. Using Fermat’s Method of Descent Descent: Let n ≥ 1. Assume that P (n) is false, so that 4n (8m + 7) = x2 + y 2 + z 2 ,

for some x, y, z ∈ Z.

Then clearly 4 | x2 + y 2 + z 2 . A simple proof by cases mod 4 (detail omitted) s...