Question? Leave a message!




Proof by Induction

Proof by Induction
ECE 250 Algorithms and Data Structures Proof by Induction Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Proof by Induction 2 Outline This topic gives an overview of the mathematical technique of a proof by induction – We will describe the inductive principle – Look at ten different examples – Four examples where the technique is incorrectly applied – Wellordering of the natural numbers – Strong induction – Geometric problemsProof by Induction 3 1.4 Definition Suppose we have a formula F(n) which we wish to show is true for all values n ≥ n 0 – Usually n = 0 or n = 1 0 0 For example, we may wish to show that n nn1  F n k   2 k0 for all n ≥ 0Proof by Induction 4 1.4 Definition We then proceed by: – Demonstrating that F(n ) is true 0 – Assuming that the formula F(n) is true for an arbitrary n – If we are able to demonstrate that this assumption allows us to also show that the formula is true for F(n + 1), the inductive principle allows us to conclude that the formula is true for all n ≥ n 0Proof by Induction 5 1.4 Definition Thus, if F(n ) is true, F(n + 1) is true 0 0 and, if F(n + 1) is true, F(n + 2) is true 0 0 and, if F(n + 2) is true, F(n + 3) is true 0 0 and so on, and so on, for all n ≥ n 0Proof by Induction 6 1.4.1 Formulation Often F(n) is an equation: – For example, F(n) may be an equation such as: n nn1  kn  for 0  2 k0 n 2 2k1 n for n1  k1 n kn1 2 21 for n 0  k0 It may also be a statement: 3 – The integer n – n is divisible by 3 for all n ≥ 1Proof by Induction 7 1.4.2 Examples We will now look at ten examples At each case, we will show the inductive process... Proof by Induction 8 1.4.2.1 Example 1 n nn1  k Prove that is true for n ≥ 0  2 k0 0 0 01  k 0 – When n = 0:  2 k0 n nn1  – Assume that the statement is true for a given n: k  2 k0 – We now show: nn1 k n1 k   kk  00Proof by Induction 9 1.4.2.1 Example 1 n nn1  k Prove that is true for n ≥ 0  2 k0 0 0 01  k 0 – When n = 0:  2 k0 n nn1  – Assume that the statement is true for a given n: k  2 k0 – We now show: nn1 k n1 k   kk  00 nn1   n1  2 2 n1 n n1   2 n 2 n1 n1 n 2   22Proof by Induction 10 1.4.2.2 Example 2 2 Prove that the sum of the first n odd integers is n : n 2 2k1 n for n1  k1 1 2 2k111 – When n = 1:  k1 n 2 21kn  – Assume that the statement is true for a given n:  k1 – We now show: nn1 2k1 2 n11 2k1   kk  10Proof by Induction 11 1.4.2.2 Example 2 2 Prove that the sum of the first n odd integers is n : n 2 2k1 n for n1  k1 1 2 2k111 – When n = 1:  k1 n 2 21kn  – Assume that the statement is true for a given n:  k1 – We now show: nn1 2k1 2 n11 2k1   kk  11 2  2nn11  2  2nn 21 2 nn21 2  n 1 Proof by Induction 12 1.4.2.3 Example 3 n kn1 2 2 1 Prove that for n ≥ 0  k0 0 k 0 01 2 21 21  – When n = 0: k0 n kn1 – Assume that the statement is true for a given n: 2 2 1  k0 – We now show: nn1 k n1 k 2 2 2  kk  00Proof by Induction 13 1.4.2.3 Example 3 n kn1 2 2 1 Prove that for n ≥ 0  k0 0 k 0 01 2 21 21  – When n = 0: k0 n kn1 – Assume that the statement is true for a given n: 2 2 1  k0 – We now show: nn1 k n1 k 2 2 2  kk  00 nn  11  2 21 n1  221 n2  21Proof by Induction 14 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01  Proof by Induction 15 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01   n  nn  11  kk1 k1   n n n n1 n n n n n n  11  k k10 k k n k1 k1 k1 k0  Proof by Induction 16 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01   n  nn  11   kk1 k1   n n n n1 n n n n n n  11   k k10 k k n k1 k1 k1 k0   n n   2  k k0 Proof by Induction 17 1.4.2.4 Example 4 n n  n  2 Prove that   k k0  0 n 0  0 12 – When n = 0:  k 0 k0  n n  n  2 – Assume that the statement is true for a given n:  k k0  – We now show: nn1 n1 n1 n1 n1    k01 k n kk  01   n  nn  11   kk1 k1   n n n n1 n n n n n n  11   k k10 k k n k1 k1 k1 k0   n n  nn1  2 2 2 2  k k0 Proof by Induction 18 1.4.2.5 Example 5 n1 n 1 r k r Prove that  1 r k0 1 0 1 r k r  1 – When n = 0: 1 r k0 n1 n 1 r k r – Assume that the statement is true for a given n:  1 r k0 – We now show: nn1 k n1 k r r r  kk  00Proof by Induction 19 1.4.2.5 Example 5 n1 n 1 r k r Prove that  1 r k0 1 0 1 r k r  1 – When n = 0: 1 r k0 n1 n 1 r k r – Assume that the statement is true for a given n:  1 r k0 – We now show: nn1 k n1 k r r r  kk  00 n1 1 r n1  r 1 r n1 n1 1rr  1 r  11 rr nn  11 11 r r r   1 r n1 n1 n1 n2 r rr11 r r  11 rrProof by Induction 20 1.4.2.6 Example 6 3 Prove by induction that n – n is divisible by 3 for all integers – This is slightly different • Choose a base case, say n = 0 • Next, prove that the truth of the formula for n implies the truth for n + 1 • Also, prove that the truth of the formula for n also implies the truth for n – 1 3 – When n = 0: 0 – 0 = 0 is divisible by 3 3 – Assume that the statement is true for a given n: n – 3 is divisible by 3 – We now show: 3 3 33 33 n1 n1 n 3n 3n1 n1 n1 n1 n 3n 3n1 n1  23 23  3 n n n n 3 n n n n  In both cases, the first term is divisible by 3, the second term is divisible by 3 by assumption; Consequently, their sum must also be divisible by 3Proof by Induction 21 1.4.2.6 Example 6 Of course, proofbyinduction may not always be the only approach: 3 Proving that n – n is divisible by 3 for all integers – An alternative proof could follow by observing that all integers may be written as either 3m 3m + 1 3m + 2 and then observing that 3 3 3 3 3 3 n n33 m m n n 3m1 3m1 n n 3m 2 3m 2   3m 3m1 3m1 3m 3m1 3m 2 3mmm1 31 3 2 Proof by Induction 22 1.4.2.7 Example 7 n n – 1 Prove that the derivative of x w.r.t. x is nx for n ≥ 1 using – the chain rule, and  – x1  Proof – When n = 1: the derivative of x is 1 n n – 1 – Assume that the derivative of x w.r.t. x is nx  nn1 – We now show: x x x  nn   x x x x  Proof by Induction 23 1.4.2.7 Example 7 n n – 1 Prove that the derivative of x w.r.t. x is nx for n ≥ 1 using – the chain rule, and  – x1  Proof – When n = 1: the derivative of x is 1 n n – 1 – Assume that the derivative of x w.r.t. x is nx nn1 – We now show: x x x   nn   x x x x   nn1  nx x x nn  nx x n nx 1 Proof by Induction 24 1.4.2.8 Example 8 ln n nln(n) Prove that for integer values of n ≥ 1  – When n = 1: ln(1) ln(1) 01ln(1) – Assume that ln n nln(n)  – We now show: ln n1  ln n1 ln n  Proof by Induction 25 1.4.2.8 Example 8 ln n nln(n) Prove that   for integer values of n ≥ 1 – When n = 1: ln(1) ln(1) 01ln(1) – Assume that ln n nln(n)  – We now show: ln n1  ln n1 ln n    ln n1 nln n   ln n1 nln n1  nn1ln1 Proof by Induction 26 1.4.2.9 Example 9 n 2 1 n H1 Prove that n  2 k 2 k1 0 2 10 – When n = 0: H11 0  2 k 2 k1 – Assume that the statement is true for a given n – We now show: n 11 n n 2 2 2  1 1 1 H n1  2 n k k k kk  11 k 21 Proof by Induction 27 1.4.2.9 Example 9 n 2 1 n Prove that H1 n  2 k 2 k1 0 2 10 – When n = 1: H11 0  2 k 2 k1 – Assume that the statement is true for a given n – We now show: n 11 n n 2 2 2  1 1 1 H n1  2 n k k k kk  11 k 21  n1 2 n 1 1  2 n k k 21 n1 2 n 1 1  n1 n 22 k 21 n1 2 n 1 11  n1 n 22 k 21 n n 2 n 1 n1 11 1 n1 2 2 2 2 2Proof by Induction 28 1.4.2.10 Example 10 2 nn 3 kk Prove that  kk  11 2 11 3 – When n = 1: kk  1  kk  11 – Assume that the statement is true for a given n 22 nn1 – We now show: k n1 k   kk  11 2 2 nn  n1 2 n1 k k   kk  11Proof by Induction 29 1.4.2.10 Example 10 2 nn 3 kk Prove that  kk  11 2 11 3 – When n = 1: kk  1  kk  11 – Assume that the statement is true for a given n 22 nn1 – We now show: k n1 k   kk  11 2 nn 2  n1 2 n1 k k   kk  11  nn1  n 23  n 2n1 2 n1 k    k1 2  n 2 3 2 3   n 2n1 n 2n n k   k1  n 3 2 3  n 3n 3n1 k   k1 3 n 3 nk1   k1 n 3 3 nk1   k1 n1 3  k  k1Proof by Induction 30 1.4.3 NonExamples All of these examples have been examples where proof by induction satisfies the desired result – What happens if it fails – We will look at three cases: • The inductive step fails • The initial inductive step is false • The ―proof‖ is invalidProof by Induction 31 1.4.3.1 NonExample 1 Suppose we have an incorrect formula—what happens Recall Fibonacci numbers: 1 n 0,1  Fn   F n1 F n 2 n 2   Suppose you saw that F(2) = 2 and F(3) = 3 and ask: Is F(n) = n for n ≥ 1 – When n = 1: F(1) = 1 by definition – Assume that the statement is true for all k = 1, 2, …, n: F(k) = k – However: F n11 F n F n  nn1   21 n  n 1 Thus, the formula is wrongProof by Induction 32 1.4.3.2 NonExample 2 10 n   n1 Consider the recursive formula Fn   F(k) n 0  – Can we find a closed form  k0 n1 Suppose n 1, then F n F k   k0 n2 F n 1 F k  +  k0 F n F n11 F n  or F n 21 F n  n – One may accidently conclude that Fn 2  – This is incorrect: F(1) = F(0) = 1: the base case is at n = 1 – The correct closedform formula is 10 n  Fn   n1 20 n Proof by Induction 33 1.4.3.3 NonExample 3 In opposition to the statement that ―x is a horse of a different color‖, prove all horses are the same color – A single horse has the same color as itself – Assume that all horses in a set of size n have the same color – Then, given a set of n + 1 horses h , h , …, h , h , we may group 1 2 n n + 1 them into two groups of size n: h , h , …, h and h , …, h , h 1 2 n 2 n n + 1 – By assumption, all the horses in both sets of size n are the same color – Therefore, all the horses in the set of n + 1 horses must be the same color Problem: the inductive step fails if n + 1 = 2 – Given a set of two horses Sea Horse, Barbaro, there is no overlap in the two subsets Sea Horse and Barbaro Proof by Induction 34 1.4.3.4 NonExample 4 You cannot get full eating peas – A person cannot become full eating one pea – Assume a person is not full after eating n peas – If a person has eaten n + 1 peas, this is one more than eating n peas and, by assumption, the person was not full after eating n peas and eating one more pea will not make him or her full, eitherProof by Induction 35 1.4.3.4 NonExample 4 Issues: – A person who is 130 cm in height may not be considered tall; however, one cannot argue that just because if someone is n cm is considered not tall, then adding one more centimetre will not make them tall, either – If one pea is eaten at a time, the rate of digestion may in fact equal the rate of consumption – ―Full‖ is not a well defined value, either • Hossein Rezazadeh, at his height, may have been able to clean and jerk 240 kg with every attempt • He was unable to ever achieve 265 kg • Attempts to clean and jerk weights between these two values may succeed or fail based on numerous other factorsProof by Induction 36 1.4.4 Justification The induction principle can either be assumed in a mathematical system as an axiom, or it can be derived from other axioms Alternatively, it can be deduced from other axioms, such as: – The natural numbers (0, 1, 2, 3, …) are linearly ordered – Every natural number is either 0 or the successor of another natural number – The successor is by definition greater than what it succeedsProof by Induction 37 1.4.4 Justification You may ask: ―Suppose you’ve proved some formula F(n) for by induction to be true for all n = 0, 1, 2, …; all we really showed was that F(0) is true—could it not fail for some larger value F(k) Suppose that there is a k such that F(k) is false – There must be a smallest value k 0 such that F(k – 1) is true but F(k) is false – But the inductive step showed that if F(k – 1) is true, it must also be true that F(k) is true – Thus, no such smallest k can exist – Thus, no subset of N can have F(n) be falseProof by Induction 38 1.4.5 Strong Induction A similar technique is strong induction where we replace the statement Fn () – Assume that true with F n , F n 1 , F n 2 ,, F n – Assume that         are all true 0 0 0 For example: Prove that with 3 and 7 cent coins, it is possible to make exact change for any amount greater than or equal to 12 centsProof by Induction 39 1.4.6 Geometric problems Given an n × 2 grid, d1 1 how many ways can that grid be covered in dominos d 2 2 – Come up with a formula for d , n verify that it is d 3 3 correct for 5 × 2, and prove it is true by d 5 4 induction Proof by Induction 40 1.4.6 Geometric problems Another: – Come up with a recursive formula that demonstrates that lines 2 nn  2 will divide the plane into regions and show 2 that the formula is correct using inductionProof by Induction 41 1.4.6 Geometric problems And another: n n – Demonstrate that any 2 × 2 grid with one square deleted may be tiled with triominos