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)!A(n+ 1)].As induction hypothesis, suppose thatA(n) holds.

2 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 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

3 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 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

4 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>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.

5 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,..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.

6 However, thefigure moreover suggests that1`3`5`7 version: Discrete Structuresby A. Klappenecker and H. 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 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.

7 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. 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)!]

8 A(n+ 1)]As induction hypothesis, suppose thatA(n) holds. Then,n+1Xk=1fk=fn+1+nXk=1fk=fn+1+fn+2 1 by Induction Hypothesis=fn+3 1 by definitionTherefore, the claim follows by induction (i!) = (n+ 1)! 1. (By convention, 0! = 1.)Induction Basis:Forn= (i!) = 0(0!) = 0 = 1 1 = (0 + 1)! 1, the claim holds forn= Step:As induction hypothesis (IH), suppose the claim is true ,n+1Xi=0i(i!) =nXi=0i(i!)+(n+ 1)(n+ 1)!=(n+ 1)! 1+(n+ 1)(n+ 1)!by IH=(n+ 2)(n+ 1)! 1 by factoring out (n+ 1)!=(n+ 2)! 1 by definition of !Therefore, the claim follows by induction onn.<latexit sha1_base64="iZgghZqr5zmN1 HKFNL5a01 KZMRE=">AAAEf3icdZPLbtNAFIbdJEAxtxaWbE7aAAlNLbsS 4iIFlSKhZlfUqxSn0Xg8 Tka1Z4xnXBpZfgxejB3vwoJjOy1pAiNLPjp3f7/H i0 OutG3/WqnVG3fu3lu9bz54+Ojxk7X1pydKpgllx1 SGMjnziGIhF+xYcx2yszhhJPJC dupdfC7ip5csUVyKIz2N2 TAiY8 EDTolG12i99sMVkgufCW26ml1pL8iOJkwmLLJys+ WqNBplvGfn5wJ4mzc7vbbYcjrNbadlgfstJb7Z3p sCleISW2 DLLrTsJvQA4x3 XHTjsami6KQ5 IihWzvvBTWuTBHlFcfcjhi0ygJXp2y3Jd85 ALymA2tl+Mtaux2 NFu29W76L7t9Nr2bJEu6 AkDGhIewUSGvoJgrufAevPfHQ41i3 GFTwr4jW8yjSX2w+Wg3d/vdEGlcSwVmxuCIZ2kbD YGQSAx0 TVdj425yEjIx+J1bs6xy5 BZXn2I+bIHmVsKlyXMz2 EZcQ5bUFKuUCOWxZprDRYyK0Gg1 PFWvjeF/n5eNcLUnev8bedWCaYFhGqZcDEGmWq4n jRXiUWwVOWzgAte4pMBVjVNlwn/hgTiSRjCYvNKB TIM5 XdV7 PYXPj4 FUHO0tmlbdnlg2 XBmxqYxOwejtZ+uL2ka4U+I7 ZUaOHashxlJNKchQzFSxWJCL8iYDdAUJGJqmJWIc niBHr9UM5 BCQ+mdr8hIpNQ08jAzInqiFmOF81+xQaqDd8 OMizjVTNBqUJCGoCUUlxF8njCqQwTICU0 QIAU6 IQlqgFe2gOAsfvKycbJjObblfN3Z3P04w7

9 FqPDc2jLbhGG+NXWPfODCODVr7Xd+ob9W7jZXGq4 bVsKvU2sqs5plx6zTe/wH/I1z6</latexit> <latexit sha1_base64="iZgghZqr5zmN1 HKFNL5a01 KZMRE=">AAAEf3icdZPLbtNAFIbdJEAxtxaWbE7aAAlNLbsS 4iIFlSKhZlfUqxSn0Xg8 Tka1Z4xnXBpZfgxejB3vwoJjOy1pAiNLPjp3f7/H i0 OutG3/WqnVG3fu3lu9bz54+Ojxk7X1pydKpgllx1 SGMjnziGIhF+xYcx2yszhhJPJC dupdfC7ip5csUVyKIz2N2 TAiY8 EDTolG12i99sMVkgufCW26ml1pL8iOJkwmLLJys+ WqNBplvGfn5wJ4mzc7vbbYcjrNbadlgfstJb7Z3p sCleISW2 DLLrTsJvQA4x3 XHTjsami6KQ5 IihWzvvBTWuTBHlFcfcjhi0ygJXp2y3Jd85 ALymA2tl+Mtaux2 NFu29W76L7t9Nr2bJEu6 AkDGhIewUSGvoJgrufAevPfHQ41i3 GFTwr4jW8yjSX2w+Wg3d/vdEGlcSwVmxuCIZ2kbD YGQSAx0 TVdj425yEjIx+J1bs6xy5 BZXn2I+bIHmVsKlyXMz2 EZcQ5bUFKuUCOWxZprDRYyK0Gg1 PFWvjeF/n5eNcLUnev8bedWCaYFhGqZcDEGmWq4n jRXiUWwVOWzgAte4pMBVjVNlwn/hgTiSRjCYvNKB TIM5 XdV7 PYXPj4 FUHO0tmlbdnlg2 XBmxqYxOwejtZ+uL2ka4U+I7 ZUaOHashxlJNKchQzFSxWJCL8iYDdAUJGJqmJWIc niBHr9UM5 BCQ+mdr8hIpNQ08jAzInqiFmOF81+xQaqDd8 OMizjVTNBqUJCGoCUUlxF8njCqQwTICU0 QIAU6 IQlqgFe2gOAsfvKycbJjObblfN3Z3P04w7 FqPDc2jLbhGG+NXWPfODCODVr7Xd+ob9W7jZXGq4 bVsKvU2sqs5plx6zTe/wH/I1z6</latexit> <latexit sha1_base64="iZgghZqr5zmN1 HKFNL5a01 KZMRE=">AAAEf3icdZPLbtNAFIbdJEAxtxaWbE7aAAlNLbsS 4iIFlSKhZlfUqxSn0Xg8 Tka1Z4xnXBpZfgxejB3vwoJjOy1pAiNLPjp3f7/H i0 OutG3/WqnVG3fu3lu9bz54+Ojxk7X1pydKpgllx1 SGMjnziGIhF+xYcx2yszhhJPJC dupdfC7ip5csUVyKIz2N2 TAiY8 EDTolG12i99sMVkgufCW26ml1pL8iOJkwmLLJys+ WqNBplvGfn5wJ4mzc7vbbYcjrNbadlgfstJb7Z3p sCleISW2 DLLrTsJvQA4x3 XHTjsami6KQ5 IihWzvvBTWuTBHlFcfcjhi0ygJXp2y3Jd85 ALymA2tl+Mtaux2 NFu29W76L7t9Nr2bJEu6 AkDGhIewUSGvoJgrufAevPfHQ41i3 GFTwr4jW8yjSX2w+Wg3d/vdEGlcSwVmxuCIZ2kbD YGQSAx0 TVdj425yEjIx+J1bs6xy5 BZXn2I+bIHmVsKlyXMz2 EZcQ5bUFKuUCOWxZprDRYyK0Gg1 PFWvjeF/n5eNcLUnev8bedWCaYFhGqZcDEGmWq4n jRXiUWwVOWzgAte4pMBVjVNlwn/hgTiSRjCYvNKB TIM5 XdV7 PYXPj4 FUHO0tmlbdnlg2 XBmxqYxOwejtZ+uL2ka4U+I7 ZUaOHashxlJNKchQzFSxWJCL8iYDdAUJGJqmJWIc niBHr9UM5 BCQ+mdr8hIpNQ08jAzInqiFmOF81+xQaqDd8

10 OMizjVTNBqUJCGoCUUlxF8njCqQwTICU0 QIAU6 IQlqgFe2gOAsfvKycbJjObblfN3Z3P04w7 FqPDc2jLbhGG+NXWPfODCODVr7Xd+ob9W7jZXGq4 bVsKvU2sqs5plx6zTe/wH/I1z6</latexit> <latexit sha1_base64="iZgghZqr5zmN1 HKFNL5a01 KZMRE=">AAAEf3icdZPLbtNAFIbdJEAxtxaWbE7aAAlNLbsS 4iIFlSKhZlfUqxSn0Xg8 Tka1Z4xnXBpZfgxejB3vwoJjOy1pAiNLPjp3f7/H i0 OutG3/WqnVG3fu3lu9bz54+Ojxk7X1pydKpgllx1 SGMjnziGIhF+xYcx2yszhhJPJC dupdfC7ip5csUVyKIz2N2 TAiY8 EDTolG12i99sMVkgufCW26ml1pL8iOJkwmLLJys+ WqNBplvGfn5wJ4mzc7vbbYcjrNbadlgfstJb7Z3p sCleISW2 DLLrTsJvQA4x3 XHTjsami6KQ5 IihWzvvBTWuTBHlFcfcjhi0ygJXp2y3Jd85 ALymA2tl+Mtaux2 NFu29W76L7t9Nr2bJEu6 AkDGhIewUSGvoJgrufAevPfHQ41i3 GFTwr4jW8yjSX2w+Wg3d/vdEGlcSwVmxuCIZ2kbD YGQSAx0 TVdj425yEjIx+J1bs6xy5 BZXn2I+bIHmVsKlyXMz2 EZcQ5bUFKuUCOWxZprDRYyK0Gg1 PFWvjeF/n5eNcLUnev8bedWCaYFhGqZcDEGmWq4n jRXiUWwVOWzgAte4pMBVjVNlwn/hgTiSRjCYvNKB TIM5 XdV7 PYXPj4 FUHO0tmlbdnlg2 XBmxqYxOwejtZ+uL2ka4U+I7 ZUaOHashxlJNKchQzFSxWJCL8iYDdAUJGJqmJWIc niBHr9UM5 BCQ+mdr8hIpNQ08jAzInqiFmOF81+xQaqDd8 OMizjVTNBqUJCGoCUUlxF8njCqQwTICU0 QIAU6 IQlqgFe2gOAsfvKycbJjObblfN3Z3P04w7 FqPDc2jLbhGG+NXWPfODCODVr7Xd+ob9W7jZXGq4 bVsKvU2sqs5plx6zTe/wH/I1z6</latexit>DivisibilityTheorem: For all positive integers n, the number 7n-2nis divisible by 5.