CSCE 222 Discrete Structures for Computing - …

1 CSCE 222 discrete structures for computing Proof by InductionDr. Hyunyoung LeeBased on slides by Andreas Klappenecker 1 MotivationInduction is an axiom which allows us to prove that certain properties are true for all positive integers (or for all nonnegative integers, or all integers >= some fixed number) 2 Induction PrincipleLet A(n) be an assertion concerning the integer we want to show that A(n) holds for all positive integer n, we can proceed as follows: Induction basis: Show that the assertion A(1) holds. Induction step: For all positive integers n, show that A(n) implies A(n+1). 3 Standard Example:Sum of the First n Positive Integers (1/2) 4 For alln 1, we havePnk=1k=n(n+ 1)/2We prove this by (n) be the claimed Step: We need to show thatA(1) 1, we haveP1k=1k= 1 = 1(1 + 1) of the First n Positive Integers (2/2) 5 Induction Step: We need to show that8n 1:[A(n)!]

2 A(n+ 1)].As induction hypothesis, suppose thatA(n) holds. Then,n+1Xk=1k=nXk=1k+(n+ 1) by definition ofX=n(n+ 1)2+2(n+ 1)2by induction hypothesis=(n+ 1)(n+ 2)2by factoring out (n+ 1)Therefore, the claim follows by induction onn.<latexit sha1_base64="iZORPDk58 DGQu2erR2 UXQDM6 JbQ=">AAAD0 HicbVNLb9 NAEHYSHsU82sKRy4iGqqVVFOcCqhTUigsckAr0 JWVDtF6P7 VXWu2Z3 TRsZC3Hl53 HjD/A7 WDtR1bQd2db425lvZr/ZDXPBje33/7banTt3791f eeA/fPT4yera+tMTowrN8 JgpofRZSA0 KLvHYcivwLNdIs1 DgaTh9V6+ffkdtuJJHdpbjOKOJ5 DFn1 Dpost76R6 TiMkJp/Q8yKlgNwxeL+R6cIkjECKwCk6pzsCm10 CWx0lQIkCRBCPZgdLAlt4nmSWqp1i7M/e8E2+Nuj xD/wAC/ZE1nubIpGm52wRR5rgwuOGuKLqRKRKYHR ynKXZ+EmHBZUsET+aryiSmySTkdBtXX0tFXU9gcQ kkaAUqNUQVLEdW02mnaAPKtoBEQixe2 DGcQYcwlb9pRMcyzXJ+bw2 WuWFNW yoahKgdVtTNHBpfIEu/VVFfjth27hLrKnKZhcZ/B TSqXHlNmleYyAVVY12IT7

3 ROU0aUaTiKNbg646wREYILyDGIlhDo3yx24pyu7P X+yttHv9 RuDm06wcDa8hR1O1v6 QSLE icwfD0 RszCvq5 HZdUW84 EuoEUBnPKpjTBkXMlzdCMy0aICl46 JHINafdKCw16 NaOkmTGzLHSRGbWpub5Wg7etjQobvxmXXOaFRcnm heJC1Ee0Pt0 QcY3 MCjdnTpl2c2bAUuo0t+4O1 CIE17d80zkZ9IJ+L/g02Nh/u5 BjxXvuvfC2vMB77e17771D79hj7Y9t0/7 RrjqfOxedn51f89B2a5 HzzFuyzu//cEg3Wg==</latexit> <latexit sha1_base64="iZORPDk58 DGQu2erR2 UXQDM6 JbQ=">AAAD0 HicbVNLb9 NAEHYSHsU82sKRy4iGqqVVFOcCqhTUigsckAr0 JWVDtF6P7 VXWu2Z3 TRsZC3Hl53 HjD/A7 WDtR1bQd2db425lvZr/ZDXPBje33/7banTt3791f eeA/fPT4yera+tMTowrN8 JgpofRZSA0 KLvHYcivwLNdIs1 DgaTh9V6+ffkdtuJJHdpbjOKOJ5 DFn1 Dpost76R6 TiMkJp/Q8yKlgNwxeL+R6cIkjECKwCk6pzsCm10 CWx0lQIkCRBCPZgdLAlt4nmSWqp1i7M/e8E2+Nuj xD/wAC/ZE1nubIpGm52wRR5rgwuOGuKLqRKRKYHR ynKXZ+EmHBZUsET+aryiSmySTkdBtXX0tFXU9gcQ kkaAUqNUQVLEdW02mnaAPKtoBEQixe2 DGcQYcwlb9pRMcyzXJ+bw2 WuWFNW yoahKgdVtTNHBpfIEu/VVFfjth27hLrKnKZhcZ/B TSqXHlNmleYyAVVY12IT7 ROU0aUaTiKNbg646wREYILyDGIlhDo3yx24pyu7P X+yttHv9 RuDm06wcDa8hR1O1v6 QSLE icwfD0 RszCvq5 HZdUW84 EuoEUBnPKpjTBkXMlzdCMy0aICl46 JHINafdKCw16 NaOkmTGzLHSRGbWpub5Wg7etjQobvxmXXOaFRcnm heJC1Ee0Pt0 QcY3 MCjdnTpl2c2bAUuo0t+4O1 CIE17d80zkZ9IJ+L/g02Nh/u5 BjxXvuvfC2vMB77e17771D79hj7Y9t0/7 RrjqfOxedn51f89B2a5

4 HzzFuyzu//cEg3Wg==</latexit> <latexit sha1_base64="iZORPDk58 DGQu2erR2 UXQDM6 JbQ=">AAAD0 HicbVNLb9 NAEHYSHsU82sKRy4iGqqVVFOcCqhTUigsckAr0 JWVDtF6P7 VXWu2Z3 TRsZC3Hl53 HjD/A7 WDtR1bQd2db425lvZr/ZDXPBje33/7banTt3791f eeA/fPT4yera+tMTowrN8 JgpofRZSA0 KLvHYcivwLNdIs1 DgaTh9V6+ffkdtuJJHdpbjOKOJ5 DFn1 Dpost76R6 TiMkJp/Q8yKlgNwxeL+R6cIkjECKwCk6pzsCm10 CWx0lQIkCRBCPZgdLAlt4nmSWqp1i7M/e8E2+Nuj xD/wAC/ZE1nubIpGm52wRR5rgwuOGuKLqRKRKYHR ynKXZ+EmHBZUsET+aryiSmySTkdBtXX0tFXU9gcQ kkaAUqNUQVLEdW02mnaAPKtoBEQixe2 DGcQYcwlb9pRMcyzXJ+bw2 WuWFNW yoahKgdVtTNHBpfIEu/VVFfjth27hLrKnKZhcZ/B TSqXHlNmleYyAVVY12IT7 ROU0aUaTiKNbg646wREYILyDGIlhDo3yx24pyu7P X+yttHv9 RuDm06wcDa8hR1O1v6 QSLE icwfD0 RszCvq5 HZdUW84 EuoEUBnPKpjTBkXMlzdCMy0aICl46 JHINafdKCw16 NaOkmTGzLHSRGbWpub5Wg7etjQobvxmXXOaFRcnm heJC1Ee0Pt0 QcY3 MCjdnTpl2c2bAUuo0t+4O1 CIE17d80zkZ9IJ+L/g02Nh/u5 BjxXvuvfC2vMB77e17771D79hj7Y9t0/7 RrjqfOxedn51f89B2a5 HzzFuyzu//cEg3Wg==</latexit> <latexit sha1_base64="iZORPDk58 DGQu2erR2 UXQDM6 JbQ=">AAAD0 HicbVNLb9 NAEHYSHsU82sKRy4iGqqVVFOcCqhTUigsckAr0 JWVDtF6P7 VXWu2Z3 TRsZC3Hl53 HjD/A7 WDtR1bQd2db425lvZr/ZDXPBje33/7banTt3791f eeA/fPT4yera+tMTowrN8 JgpofRZSA0 KLvHYcivwLNdIs1 DgaTh9V6+ffkdtuJJHdpbjOKOJ5 DFn1 Dpost76R6

5 TiMkJp/Q8yKlgNwxeL+R6cIkjECKwCk6pzsCm10 CWx0lQIkCRBCPZgdLAlt4nmSWqp1i7M/e8E2+Nuj xD/wAC/ZE1nubIpGm52wRR5rgwuOGuKLqRKRKYHR ynKXZ+EmHBZUsET+aryiSmySTkdBtXX0tFXU9gcQ kkaAUqNUQVLEdW02mnaAPKtoBEQixe2 DGcQYcwlb9pRMcyzXJ+bw2 WuWFNW yoahKgdVtTNHBpfIEu/VVFfjth27hLrKnKZhcZ/B TSqXHlNmleYyAVVY12IT7 ROU0aUaTiKNbg646wREYILyDGIlhDo3yx24pyu7P X+yttHv9 RuDm06wcDa8hR1O1v6 QSLE icwfD0 RszCvq5 HZdUW84 EuoEUBnPKpjTBkXMlzdCMy0aICl46 JHINafdKCw16 NaOkmTGzLHSRGbWpub5Wg7etjQobvxmXXOaFRcnm heJC1Ee0Pt0 QcY3 MCjdnTpl2c2bAUuo0t+4O1 CIE17d80zkZ9IJ+L/g02Nh/u5 BjxXvuvfC2vMB77e17771D79hj7Y9t0/7 RrjqfOxedn51f89B2a5 HzzFuyzu//cEg3Wg==</latexit>The Main PointsWe established in the induction basis that the assertion A(1) is showed in the induction step that A(n+1) holds, assuming that A(n) holds.

6 In other words, we showed in the induction step that A(n) A(n+1) holds for all n >= 1. 6 Perfect SquaresThe perfect squares are given by12=1, 22=4, 32=9, 42=16, .. (n+1)2 = n2+n+n+1 = n2+2n+1 1+3+5+7 = 42 Chapter 4 Proofs by InductionI think some intuition leaks out in every step of an induction proof. Jim Propp, talk at AMS special session, January 2000 The principle of induction and the related principle of strong induction havebeen introduced in the previous chapter. However, it takes a bit of practiceto understand how to formulate such proofs. In this chapter, we will illustrateboth methods with several Perfect SquaresThe perfect squares are given by12 1,22 4,32 9,42 16.

7 Figure depicts the perfect squares graphically. Figure :The first four perfect squares are 1, 4, 9, and 16. The illustrationexplains why these are also known as square numbers. The number of squares withoutan asterisk in the subfigures are 1, 3, 5, and figure makes it apparent that going from the perfect squaren2to thenext, we have to addnsquares on top,nsquares on the side, and 1 for thecorner; hence,pn`1q2 n2`2n`1,a fact that we could have just as easily obtained by algebra. However, thefigure moreover suggests that1`3`5`7 version: Discrete Structuresby A. Klappenecker and H.

8 Lee, 2014-2019113 7 Example 2 Theorem: For all positive integers n, we have 1+3+5+..+(2n-1) = n2 Proof. We prove this by induction on n. Let A(n) be the assertion of the basis: Since 1 = 12, it follows that A(1) holds. Induction step: As induction hypothesis (IH), suppose that A(n) holds. Then1+3+5+..+(2n-1)+(2n+1) = n2+(2n+1) = (n+1)2holds. In other words, A(n) implies A(n+1). Therefore, the claim follows by induction on n. 8by IHExample 3 Theorem: We have 12 + 22 + .. + n2 = n(n+1)(2n+1)/6for all n >= 1. Proof. Your turn!!!Let B(n) denote the assertion of the theorem. Induction basis:Since 12 = 1(1+1)(2+1)/6, we can conclude that B(1) holds.

9 9 Example 3 (Cont.)Inductive step: As induction hypothesis (IH), suppose that B(n) holds. Then 12 + 22 + .. + n2 + (n+1)2 = n(n+1)(2n+1)/6 + (n+1)2 by IHFactoring out (n+1) on the right hand side yields (n+1)(n(2n+1)+6(n+1))/6 = (n+1)(2n2 +7n+6)/6 One easily verifies that this is equal to (n+1)(n+2)(2n+3)/6 = (n+1)((n+1)+1)(2(n+1)+1)/6 Thus, B(n+1) holds. Therefore, the claim follows by induction on n. 10 Example 4 Theorem: We have 13 + 23 + .. + n3 = n2(n+1)2/4for all n >= 1. Proof. Let P(n) denote the assertion of the theorem. Induction basis: Show that P(1) 13 = 12(1+1)2/4, we conclude that P(1) holds.

10 11 Example 4 (Cont.)Inductive step: As induction hypothesis (IH), suppose that P(n) holds. Then 13 + 23 + .. + n3 + (n+1)3= n2(n+1)2/4 + (n+1)3 by IHFactoring out (n+1)2 on the right hand side yields (n+1)2(n2+4(n+1))/4 = (n+1)2(n2 +4n+4)/4 = (n+1)2(n+2)2/4which is equal to (n+1)2((n+1)+1)2/4 Thus, P(n+1) holds. Therefore, the claim follows by induction on n. 12 TipHow can you verify whether your algebra is correct? Use [Not allowed in any exams, though. Sorry!] 13 More Examples 14 Sum of Fibonacci Numbers (1/2)Letf0= 0 andf1= 1 andfn=fn 1+fn 2forn 2. ThennXk=1fk=fn+2 basis: Forn= 1, we have1Xk=1fk= 1 = (1 + 1) 1=f1+f2 1=f3 1 15 Sum of Fibonacci Numbers (2/2) 16 LetA(n) be the claimed Step: We need to show that8n 1:[A(n)!]