17-mathematical-induction_in discrete_math.ppt

discrete math

1. 11
Mathematical InductionMathematical Induction
CS/APMA 202CS/APMA 202
Rosen section 3.3Rosen section 3.3
Aaron BloomfieldAaron Bloomfield

2. 22
What is induction?What is induction?
A method of proofA method of proof
It does not generate answers: It does not generate answers:
it only can prove themit only can prove them
Three parts:Three parts:

Base case(s): show it is true Base case(s): show it is true
for one elementfor one element

Inductive hypothesis: assume Inductive hypothesis: assume
it is true for any given elementit is true for any given element
Must be clearly labeled!!!Must be clearly labeled!!!

Show that if it true for the next Show that if it true for the next
highest elementhighest element

3. 33
Show that the sum of the first Show that the sum of the first nn odd odd
integers is integers is nn
22

Example: If Example: If nn = 5, 1+3+5+7+9 = 25 = 5 = 5, 1+3+5+7+9 = 25 = 5
22

Formally, ShowFormally, Show
Base case: Show that P(1) is trueBase case: Show that P(1) is true
Induction exampleInduction example



n
i
ni
1
2
12
11
11)(2
1
1
2


i
i
 )P( where)P( nnn
)1P(


4. 44
Inductive hypothesis: assume true for Inductive hypothesis: assume true for kk

Thus, we assume that P(Thus, we assume that P(kk) is true, or that) is true, or that

Note: we don’t yet know if this is true or not!Note: we don’t yet know if this is true or not!
Inductive step: show true for Inductive step: show true for kk+1+1

We want to show that: We want to show that:



k
i
ki
1
2
12




1
1
2
)1(12
k
i
ki
Induction example, continuedInduction example, continued

5. 55
12121)1(2
2
1


kkik
k
i
121)1(2
22
 kkkk
Induction example, continuedInduction example, continued
Recall the inductive hypothesis:Recall the inductive hypothesis:
Proof of inductive step:Proof of inductive step:



k
i
ki
1
2
12
1212
22
 kkkk
2
1
1
)1(12 


ki
k
i

6. 66
What did we showWhat did we show
Base case: P(1)Base case: P(1)
If P(If P(kk) was true, then P() was true, then P(kk+1) is true+1) is true

i.e., P(i.e., P(kk) → P() → P(kk+1)+1)
We know it’s true for P(1)We know it’s true for P(1)
Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(1), then it’s true for P(2)+1), if it’s true for P(1), then it’s true for P(2)
Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(2), then it’s true for P(3)+1), if it’s true for P(2), then it’s true for P(3)
Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(3), then it’s true for P(4)+1), if it’s true for P(3), then it’s true for P(4)
Because of P(Because of P(kk) → P() → P(kk+1), if it’s true for P(4), then it’s true for P(5)+1), if it’s true for P(4), then it’s true for P(5)
And onwards to infinityAnd onwards to infinity
Thus, it is true for all possible values of Thus, it is true for all possible values of nn
In other words, we showed that:In other words, we showed that:
   )P()1P()P()1P( nnkkk 

7. 77
The idea behind inductive proofsThe idea behind inductive proofs
Show the base caseShow the base case
Show the inductive hypothesisShow the inductive hypothesis
Manipulate the inductive step so that you Manipulate the inductive step so that you
can substitute in part of the inductive can substitute in part of the inductive
hypothesishypothesis
Show the inductive stepShow the inductive step

8. 8
Quick surveyQuick survey

I felt I understood the first example of I felt I understood the first example of
induction…induction…
a)a)Very wellVery well
b)b)With some review, I’ll be goodWith some review, I’ll be good
c)c)Not reallyNot really
d)d)Not at allNot at all

9. 9
Quick surveyQuick survey

I felt I could do my own inductive proof…I felt I could do my own inductive proof…
a)a)Very wellVery well
b)b)With some review, I’ll be goodWith some review, I’ll be good
c)c)Not reallyNot really
d)d)Not at allNot at all

10. 1010
Why speling is not so important…Why speling is not so important…
I cdnuolt blveieetaht I cluod aulaclty uesdnatnrd I cdnuolt blveieetaht I cluod aulaclty uesdnatnrd
waht I was rdanieg. The phaonmneal pweor of waht I was rdanieg. The phaonmneal pweor of
thehmuan mind. Aoccdrnig to a rscheearch at thehmuan mind. Aoccdrnig to a rscheearch at
Cmabrigde Uinervtisy, it deosn't mttaer in waht Cmabrigde Uinervtisy, it deosn't mttaer in waht
oredr the ltteers in a wrod are, the olny oredr the ltteers in a wrod are, the olny
iprmoatnt tihng is taht thefrist and lsat ltteer be iprmoatnt tihng is taht thefrist and lsat ltteer be
in the rghit pclae. The rset can be a taotl mses in the rghit pclae. The rset can be a taotl mses
andyou can sitll raed it wouthit a porbelm. Tihs is andyou can sitll raed it wouthit a porbelm. Tihs is
bcuseae the huamn mnid deosnot raed ervey bcuseae the huamn mnid deosnot raed ervey
lteter by istlef, but the wrod as a wlohe. Amzanig lteter by istlef, but the wrod as a wlohe. Amzanig
huh? yaeh and I awlyas thought slpeling was huh? yaeh and I awlyas thought slpeling was
ipmorantt.ipmorantt.

11. 1111
Second induction exampleSecond induction example
Rosen, section 3.3, question 2:Rosen, section 3.3, question 2:

Show the sum of the first Show the sum of the first nn positive even positive even
integers is integers is nn
22
+ + nn

Rephrased: Rephrased:
The three parts:The three parts:

Base caseBase case

Inductive hypothesisInductive hypothesis

Inductive stepInductive step



n
i
nninnn
1
2
2)P( where)P(

12. 1212
Second induction example, Second induction example,
continuedcontinued
Base case: Show P(1):Base case: Show P(1):
Inductive hypothesis: Assume Inductive hypothesis: Assume
Inductive step: Show Inductive step: Show
22
11)(2)1P(
1
1
2


i
i



k
i
kkik
1
2
2)P(
)1()1(2)1P(
2
1
1



kkik
k
i

13. 1313
2323
22
 kkkk
1)1()1(2
22
 kkkkk
1)1(2)1(2
2
1


kkik
k
i
1)1(2
2
1
1



kki
k
i
Second induction example, Second induction example,
continuedcontinued
Recall our inductive Recall our inductive
hypothesis:hypothesis:



k
i
kkik
1
2
2)P(

14. 1414
Notes on proofs by inductionNotes on proofs by induction
We manipulate the We manipulate the kk+1 case to make part +1 case to make part
of it look like the of it look like the kk case case
We then replace that part with the other We then replace that part with the other
side of the side of the kk case case



k
i
kkik
1
2
2)P(
2323
22
 kkkk
1)1()1(2
22
 kkkkk
1)1(2)1(2
2
1


kkik
k
i
1)1(2
2
1
1



kki
k
i

15. 1515
Third induction exampleThird induction example
Rosen, question 7: ShowRosen, question 7: Show
Base case: Base case: nn = 1 = 1
Inductive hypothesis: assume Inductive hypothesis: assume
6
)12)(1(
1
2 


nnn
i
n
i
11
6
6
1
6
)12)(11(1
2
1
1
2




i
i
6
)12)(1(
1
2 


kkk
i
k
i

16. 1616
Third induction exampleThird induction example
Inductive step: show Inductive step: show
6
)1)1(2)(1)1)((1(
1
1
2 



kkk
i
k
i
6
)32)(2)(1(
)1(
1
22 


kkk
ik
k
i
6139261392
2323
 kkkkkk
)32)(2)(1()12)(1()1(6
2
 kkkkkkk
6
)32)(2)(1(
6
)12)(1(
)1(
2 



kkkkkk
k
6
)1)1(2)(1)1)((1(
1
1
2 



kkk
i
k
i
6
)12)(1(
1
2 


kkk
i
k
i

17. 1717
Third induction again: what if your Third induction again: what if your
inductive hypothesis was wrong?inductive hypothesis was wrong?
Show:Show:
Base case: Base case: nn = 1: = 1:
But let’s continue anyway…But let’s continue anyway…
Inductive hypothesis: assume Inductive hypothesis: assume
6
)22)(1(
1
2 


nnn
i
n
i
6
7
1
6
7
1
6
)22)(11(1
2
1
1
2




i
i
6
)22)(1(
1
2 


kkk
i
k
i

18. 1818
Third induction again: what if your Third induction again: what if your
inductive hypothesis was wrong?inductive hypothesis was wrong?
Inductive step: show Inductive step: show
6
)2)1(2)(1)1)((1(
1
1
2 



kkk
i
k
i
6
)42)(2)(1(
)1(
1
22 


kkk
ik
k
i
816102614102
2323
 kkkkkk
)42)(2)(1()22)(1()1(6
2
 kkkkkkk
6
)42)(2)(1(
6
)22)(1(
)1(
2 



kkkkkk
k
6
)2)1(2)(1)1)((1(
1
1
2 



kkk
i
k
i
6
)22)(1(
1
2 


kkk
i
k
i

19. 1919
Fourth induction exampleFourth induction example
Rosen, question 14: show that Rosen, question 14: show that nn! < ! < nn
nn
for for
all all nn > 1 > 1
Base case: Base case: nn = 2 = 2
2! < 22! < 2
22
2 < 42 < 4
Inductive hypothesis: assume Inductive hypothesis: assume kk! < ! < kk
kk
Inductive step: show that (Inductive step: show that (kk+1)! < (+1)! < (kk+1)+1)
kk+1+1
)!1(k !)1(kk
k
kk)1(
k
kk )1)(1( 
1
)1(


k
k

20. 20
Quick surveyQuick survey

I felt I understand induction…I felt I understand induction…
a)a)Very wellVery well
b)b)With some review, I’ll be goodWith some review, I’ll be good
c)c)Not reallyNot really
d)d)Not at allNot at all

21. 2121
Strong inductionStrong induction
Weak mathematical induction assumes Weak mathematical induction assumes
P(P(kk) is true, and uses that (and only that!) ) is true, and uses that (and only that!)
to show P(to show P(kk+1) is true+1) is true
Strong mathematical induction assumes Strong mathematical induction assumes
P(1), P(2), …, P(P(1), P(2), …, P(kk) are all true, and uses ) are all true, and uses
that to show that P(that to show that P(kk+1) is true.+1) is true.
  )1P()P(...)3P()2P()1P(  kk

22. 2222
Strong induction example 1Strong induction example 1
Show that any number > 1 can be written Show that any number > 1 can be written
as the product of primesas the product of primes
Base case: P(2)Base case: P(2)

2 is the product of 2 (remember that 1 is not 2 is the product of 2 (remember that 1 is not
prime!)prime!)
Inductive hypothesis: P(1), P(2), P(3), …, Inductive hypothesis: P(1), P(2), P(3), …,
P(P(kk) are all true) are all true
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true

23. 2323
Strong induction example 1Strong induction example 1
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true
There are two cases:There are two cases:

kk+1 is prime+1 is prime
It can then be written as the product of It can then be written as the product of kk+1+1

kk+1 is composite+1 is composite
It can be written as the product of two composites, It can be written as the product of two composites,
a and b, where 2 ≤ a and b, where 2 ≤ aa ≤ ≤ bb < < kk+1+1
By the inductive hypothesis, both P(By the inductive hypothesis, both P(aa) and P() and P(bb) are ) are
truetrue

24. 2424
Strong induction vs. non-strong Strong induction vs. non-strong
inductioninduction
Rosen, question 31: Determine which Rosen, question 31: Determine which
amounts of postage can be written with 5 amounts of postage can be written with 5
and 6 cent stampsand 6 cent stamps

Prove using both versions of inductionProve using both versions of induction

Similar to example 15 (page 250)Similar to example 15 (page 250)
Answer: any postage ≥ 20Answer: any postage ≥ 20

25. 2525
Answer via mathematical inductionAnswer via mathematical induction
Show base case: P(20):Show base case: P(20):

20 = 5 + 5 + 5 + 520 = 5 + 5 + 5 + 5
Inductive hypothesis: Assume P(Inductive hypothesis: Assume P(kk) is true) is true
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true

If P(If P(kk) uses a 5 cent stamp, replace that stamp with a ) uses a 5 cent stamp, replace that stamp with a
6 cent stamp6 cent stamp

If P(If P(kk) does not use a 5 cent stamp, it must use only 6 ) does not use a 5 cent stamp, it must use only 6
cent stampscent stamps
Since Since kk > 18, there must be four 6 cent stamps > 18, there must be four 6 cent stamps
Replace these with five 5 cent stamps to obtain Replace these with five 5 cent stamps to obtain kk+1+1

26. 2626
Answer via strong inductionAnswer via strong induction
Show base cases: P(20), P(21), P(22), P(23), and P(24) Show base cases: P(20), P(21), P(22), P(23), and P(24)

20 = 5 + 5 + 5 + 520 = 5 + 5 + 5 + 5

21 = 5 + 5 + 5 + 621 = 5 + 5 + 5 + 6

22 = 5 + 5 + 6 + 622 = 5 + 5 + 6 + 6

23 = 5 + 6 + 6 + 623 = 5 + 6 + 6 + 6

24 = 6 + 6 + 6 + 624 = 6 + 6 + 6 + 6
Inductive hypothesis: Assume P(20), P(21), …, P(Inductive hypothesis: Assume P(20), P(21), …, P(kk) are ) are
all trueall true
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true

We will obtain P(We will obtain P(kk+1) by adding a 5 cent stamp to P(+1) by adding a 5 cent stamp to P(kk+1-5)+1-5)

Since we know P(Since we know P(kk+1-5) = P(+1-5) = P(kk-4) is true, our proof is complete-4) is true, our proof is complete

27. 2727
Strong induction vs. non-strong Strong induction vs. non-strong
induction, take 2induction, take 2
Rosen, section 3.4, example 15: Show Rosen, section 3.4, example 15: Show
that every postage amount 12 cents or that every postage amount 12 cents or
more can be formed using only 4 and 5 more can be formed using only 4 and 5
cent stampscent stamps
Similar to the previous exampleSimilar to the previous example

28. 2828
Answer via mathematical inductionAnswer via mathematical induction
Show base case: P(12):Show base case: P(12):

12 = 4 + 4 + 412 = 4 + 4 + 4
Inductive hypothesis: Assume P(Inductive hypothesis: Assume P(kk) is true) is true
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true

If P(If P(kk) uses a 4 cent stamp, replace that stamp with a ) uses a 4 cent stamp, replace that stamp with a
5 cent stamp to obtain 5 cent stamp to obtain PP((kk+1)+1)

If P(If P(kk) does not use a 4 cent stamp, it must use only 5 ) does not use a 4 cent stamp, it must use only 5
cent stampscent stamps
Since Since kk > 10, there must be at least three 5 cent stamps > 10, there must be at least three 5 cent stamps
Replace these with four 4 cent stamps to obtain Replace these with four 4 cent stamps to obtain kk+1+1
Note that only Note that only PP((kk) was assumed to be true) was assumed to be true

29. 2929
Answer via strong inductionAnswer via strong induction
Show base cases: P(12), P(13), P(14), and P(15)Show base cases: P(12), P(13), P(14), and P(15)

12 = 4 + 4 + 412 = 4 + 4 + 4

13 = 4 + 4 + 513 = 4 + 4 + 5

14 = 4 + 5 + 514 = 4 + 5 + 5

15 = 5 + 5 + 515 = 5 + 5 + 5
Inductive hypothesis: Assume P(12), P(13), …, P(Inductive hypothesis: Assume P(12), P(13), …, P(kk) are all true) are all true

For For kk ≥≥ 15 15
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true

We will obtain P(We will obtain P(kk+1) by adding a 4 cent stamp to P(+1) by adding a 4 cent stamp to P(kk+1-4)+1-4)

Since we know P(Since we know P(kk+1-4) = P(+1-4) = P(kk-3) is true, our proof is complete-3) is true, our proof is complete
Note that P(12), P(13), …, P(Note that P(12), P(13), …, P(kk) were all assumed to be true) were all assumed to be true

30. 30
Quick surveyQuick survey

I felt I understand strong vs. weak induction…I felt I understand strong vs. weak induction…
a)a)Very wellVery well
b)b)With some review, I’ll be goodWith some review, I’ll be good
c)c)Not reallyNot really
d)d)Not at allNot at all

31. 3131
An aside: IOCCCAn aside: IOCCC

The International Obfuscated C Code The International Obfuscated C Code
ContestContest
–Online at http://www.ioccc.orgOnline at http://www.ioccc.org

C has very terse syntaxC has very terse syntax
–So the contest tries to make it terser!So the contest tries to make it terser!

One common method is by modifying the One common method is by modifying the
whitespacewhitespace

32. 3232
X XX X
X X X XX X X X
X X X XX X X X
X X X XX X X X
X X X XX X X X
X X X XX X X X
X X X XX X X X
X X X X X XX X X X X X
X XX X X XX XX XX X X XX X
X XXX X XXXXXXXXX X XXX XX XXX X XXXXXXXXX X XXX X
X XXX X XXXX XXXX X XXX XX XXX X XXXX XXXX X XXX X
X XXXX X XX ainma(){ archa XX X XXXX XX XXXX X XX ainma(){ archa XX X XXXX X
X XXXX X oink[9],*igpa, X XXXX XX XXXX X oink[9],*igpa, X XXXX X
X XXXXXX atinla=etcharga(),iocccwa XXXXXX XX XXXXXX atinla=etcharga(),iocccwa XXXXXX X
X XXXX ,apca='A',owla='a',umna=26 XXXX XX XXXX ,apca='A',owla='a',umna=26 XXXX X
X XXX ; orfa(; (atinla+1)&&(!((( XXX XX XXX ; orfa(; (atinla+1)&&(!((( XXX X
X XX atinla-apca)*(apca+umna-atinla) XX XX XX atinla-apca)*(apca+umna-atinla) XX X
X X >=0)+((atinla-owla)*(owla+umna- X XX X >=0)+((atinla-owla)*(owla+umna- X X
X atinla)>=0))); utcharpa(atinla), XX atinla)>=0))); utcharpa(atinla), X
X X atinla=etcharga()); orfa(; atinla+1; X XX X atinla=etcharga()); orfa(; atinla+1; X X
X X ){ orfa( igpa=oink ,iocccwa=( X XX X ){ orfa( igpa=oink ,iocccwa=( X X
X X (atinla- XXX apca)*( XXX apca+umna- X XX X (atinla- XXX apca)*( XXX apca+umna- X X
X atinla)>=0) XXX XXX ; (((( XX atinla)>=0) XXX XXX ; (((( X
X atinla-apca XXXXX XXXXXXX XXXXX )*(apca+ XX atinla-apca XXXXX XXXXXXX XXXXX )*(apca+ X
X umna-atinla XXXXXX )>=0) XXXXXX +((atinla- XX umna-atinla XXXXXX )>=0) XXXXXX +((atinla- X
X owla)*(owla+ XXXX umna- XXXX atinla)>=0)) XX owla)*(owla+ XXXX umna- XXXX atinla)>=0)) X
X &&"-Pig-" XX "Lat-in" XX "COb-fus" XX &&"-Pig-" XX "Lat-in" XX "COb-fus" X
X "ca-tion!!"[ X (((atinla- X apca)*(apca+ XX "ca-tion!!"[ X (((atinla- X apca)*(apca+ X
X umna-atinla) X >=0)?atinla- X apca+owla: XX umna-atinla) X >=0)?atinla- X apca+owla: X
X atinla)-owla X ]-'-')||((igpa== X oink)&&!(*( XX atinla)-owla X ]-'-')||((igpa== X oink)&&!(*( X
X igpa++)='w') X )||! X (*( X igpa X ++)=owla); * XX igpa++)='w') X )||! X (*( X igpa X ++)=owla); * X
X (igpa++)=(( X ( XXX XXX X atinla-apca XX (igpa++)=(( X ( XXX XXX X atinla-apca X
X )*(apca+ X umna XXX - XXX X atinla)>=0) XX )*(apca+ X umna XXX - XXX X atinla)>=0) X
X ?atinla- X apca XXX + XXX owla X :atinla), XX ?atinla- X apca XXX + XXX owla X :atinla), X
X atinla= X X X X etcharga()) XX atinla= X X X X etcharga()) X
X ; orfa( X atinla=iocccwa?(( X (atinla- XX ; orfa( X atinla=iocccwa?(( X (atinla- X
X owla)*(owla+ X umna-atinla)>=0 X )?atinla- XX owla)*(owla+ X umna-atinla)>=0 X )?atinla- X
X owla+apca: X atinla): X atinla; ((( XX owla+apca: X atinla): X atinla; ((( X
X atinla-apca)* X (apca+umna- X atinla)>=0)+( XX atinla-apca)* X (apca+umna- X atinla)>=0)+( X
X (atinla-owla)* X (owla+ X umna-atinla)>= XX (atinla-owla)* X (owla+ X umna-atinla)>= X
X 0)); utcharpa( XX XX atinla),atinla XX 0)); utcharpa( XX XX atinla),atinla X
X =etcharga()); XXXXXXX orfa(*igpa=0, XX =etcharga()); XXXXXXX orfa(*igpa=0, X
X igpa=oink; * igpa; utcharpa( XX igpa=oink; * igpa; utcharpa( X
X *(igpa++))); orfa(; (atinla+1)&&(!((( XX *(igpa++))); orfa(; (atinla+1)&&(!((( X
X atinla-apca )*(apca+ XX atinla-apca )*(apca+ X
X umna- XXXXX XXXXX atinla)>=0 XX umna- XXXXX XXXXX atinla)>=0 X
X )+(( XXXXX atinla- XX )+(( XXXXX atinla- X
XX owla)*( owla+umna- XXXX owla)*( owla+umna- XX
XX atinla)>=0))); utcharpa XXXX atinla)>=0))); utcharpa XX
XX (atinla),atinla= XXXX (atinla),atinla= XX
XX etcharga()); } XXXX etcharga()); } XX
XXXX } XXXXXXXX } XXXX
XXXXXXXXXXXXXXXXXX
#define X#define X
#define XX#define XX
#define XXX#define XXX
#define XXXX#define XXXX
#define XXXXX#define XXXXX
#define XXXXXX#define XXXXXX
#define XXXXXXX#define XXXXXXX
#define orfa for#define orfa for
#define XXXXXXXXX#define XXXXXXXXX
#define archa char#define archa char
#define ainma main#define ainma main
#define etcharga getchar#define etcharga getchar
#define utcharpa putchar#define utcharpa putchar
#include <stdio.h>
#define Q r=R[*p++-'0'];while(
#define B ;break;case
char*s="Qjou!s\\311^-g\\311^-n\\311^-c\\::^-q-ma%mO1JBHm%BQ-aP1J[O1HB%[Q<nbj\
o)*|gps)<<*txjudi)m*|aQdbtf!::::;sfuvso<aQefgbvmu;aQ<m,,a%CQ<csfbla%bQ<aN2!Q\
\ndbtf!aP2Q;m>aP2Q<a%!D12J!JGJHJOJQJFJSJJJMHS%HD12D12N3!N4\nJUJT%UQm>aP4HC%T\
Qs\\q,,^>m,2<m>aP4HC%SD12N1\nJNQm>s\\..q^aHC%NHb%GN1!D32P3%RN1UP1D12JPQUaP1H\
R%PN4\nQ<g\\(aP3Q(^>aP2Q,2<n\\(aP3Q(^>aP4Hb%OD12D12N2!N3\nJVP3Q,,<jg)aP3Q=>n\
\\(aP3Q(^*m>g\\(aP3Q(^<fmtf!m,,aHC%QN1!N1\nJ#Qqsjoug)#&e]o#-aP1Q*aHb%#Qqvut)\
aP1Q*aHb%FN1\nQm>::::aHC%VP3Q>bupj)hfut)c**aHb%JD12JON1!Qjg)a%LN1UP1D12JIQUa\
P1HL%IQ*m>aN2!N2\nP2Q<fmtf!m,,aHC%MN1!N2>P2Q>aN2\nP2Hbdd!b/d";k;char R[4][99]
;main(c,v)char**v;{char*p,*r,*q;for(q=s;*q;q++)*q>' '&&(*q)--;{FILE*i=fopen(v
[1],"r"),*o=fopen(q-3,"w");for(p=s;;p++)switch(*p++){B'M':Q(k=fgetc(i))!=EOF
&&k!=*p)*r++=k;if(k==EOF){fputs("}}\n",o);fclose(o);return system(q-6);}*r=0
B'P':while(*p!='`')fputc(*p++,o)B'O':Q*r)fputc(*r++,o);p--B'C':k=0;Q k<*p-'0'
)(*r++=fgetc(i),k++);*r=0 B'I':k= *p;if(**R==k)goto G B'G':k= *p;G:p=s;while(
*p!='$'||p[1]!= k)p++;p++B'N':R[*p-'0'][0]++;}}}
a(X){/*/X=-a(X){/*/X=- a(X){/*/X=-a(X){/*/X=-
-1;F;X=--1;F;X=- -1;F;X=--1;F;X=-
-1;F;}/*/-1;F;}/*/ -1;F;}/*/-1;F;}/*/
char*z[]={"char*z[]={","a(X){/*/X=-","-1;F;X=-","-1;F;}/*/","9999999999 :-| ",char*z[]={"char*z[]={","a(X){/*/X=-","-1;F;X=-","-1;F;}/*/","9999999999 :-| ",
"int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*","int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*",
"z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z","z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z",
"[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(","[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(",
"9);}y(A){for(j=8;j;)~A&w[--j]||(q=0);}e(W,Z){for(i-=i*q;i<9&&q;)y(W|(1<<i++&","9);}y(A){for(j=8;j;)~A&w[--j]||(q=0);}e(W,Z){for(i-=i*q;i<9&&q;)y(W|(1<<i++&",
"~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k--],X|O);}main(u,v)char**v;{a(q=1);b(1);","~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k--],X|O);}main(u,v)char**v;{a(q=1);b(1);",
"c(1);*J=--u?O?*J:*v[1]:53;X|=u<<57-*v[u];y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X","c(1);*J=--u?O?*J:*v[1]:53;X|=u<<57-*v[u];y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X",
",O),R(),O|=1<<--i:J[*J-48+(X=O=0)]--;L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N",",O),R(),O|=1<<--i:J[*J-48+(X=O=0)]--;L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N",
";s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}",0};";s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}",0};
b(X){/*/X=-b(X){/*/X=- b(X){/*/X=-b(X){/*/X=-
-1;F;X=--1;F;X=- -1;F;X=--1;F;X=-
-1;F;}/*/-1;F;}/*/ -1;F;}/*/-1;F;}/*/
int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*int q,i,j,k,X,O=0,H;S(x)int*x;{X+=X;O+=O;*x+1?*x+2||X++:O++;*x=1;}L(n){for(*
z[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=zz[i=1]=n+97;i<4;i++)M(256),s(i),M(128),s(i),M(64),N;X*=8;O*=8;}s(R){char*r=z
[R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P([R];for(q&&Q;*r;)P(*r++);q&&(Q,P(44));}M(m){P(9);i-2||P(X&m?88:O&m?48:32);P(
9);}y(A){for(j=8;j;)~A&w[--j]||(q=0);}e(W,Z){for(i-=i*q;i<9&&q;)y(W|(1<<i++&9);}y(A){for(j=8;j;)~A&w[--j]||(q=0);}e(W,Z){for(i-=i*q;i<9&&q;)y(W|(1<<i++&
~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k--],X|O);}main(u,v)char**v;{a(q=1);b(1);~Z));}R(){for(k=J[*J-48]-40;k;)e(w[k--],X|O);}main(u,v)char**v;{a(q=1);b(1);
c(1);*J=--u?O?*J:*v[1]:53;X|=u<<57-*v[u];y(X);K=40+q;q?e(O,X),q&&(K='|'),e(Xc(1);*J=--u?O?*J:*v[1]:53;X|=u<<57-*v[u];y(X);K=40+q;q?e(O,X),q&&(K='|'),e(X
,O),R(),O|=1<<--i:J[*J-48+(X=O=0)]--;L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N,O),R(),O|=1<<--i:J[*J-48+(X=O=0)]--;L(q=0);for(s(i=0);q=i<12;)s(i++),i>4&&N
;s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);};s(q=12);P(48);P('}');P(59);N;q=0;L(1);for(i=5;i<13;)s(i++),N;L(2);}
c(X){/*/X=-c(X){/*/X=- c(X){/*/X=-c(X){/*/X=-
-1;F;X=--1;F;X=- -1;F;X=--1;F;X=-
-1;F;}/*/-1;F;}/*/ -1;F;}/*/-1;F;}/*/
An aside: IOCCCAn aside: IOCCC
#define _ -F<00||--F-OO--;#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{{
_-_-_-__-_-_-_
_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-__-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-__-_-_-_-_-_-_-_
_-_-_-__-_-_-_
}}

33. 3333
Chess and inductionChess and induction
7
6
5
4
3
2
1
0
0 1 2 3 4 5 6 7
Can the knight reach any
square in a finite number
of moves?
Show that the knight can
reach any square (i, j) for
which i+j=k where k > 1.
Base case: k = 2
Inductive hypothesis:
assume the knight can
reach any square (i, j) for
which i+j=k where k > 1.
Inductive step: show the
knight can reach any
square (i, j) for which
i+j=k+1 where k > 1.

34. 3434
Chess and inductionChess and induction
Inductive step: show the knight can reach any Inductive step: show the knight can reach any
square (square (ii, , jj) for which ) for which ii++jj==kk+1 where +1 where kk > 1. > 1.

Note that Note that kk+1 ≥ 3, and one of +1 ≥ 3, and one of ii or or jj is ≥ 2 is ≥ 2

If If ii ≥ 2, the knight could have moved from ( ≥ 2, the knight could have moved from (ii-2, -2, jj+1)+1)
Since Since ii++jj = = kk+1, +1, ii-2 + -2 + jj+1 = +1 = kk, which is assumed true, which is assumed true

If If jj ≥ 2, the knight could have moved from ( ≥ 2, the knight could have moved from (ii+1, +1, j-2j-2))
Since Since ii++jj = = kk+1, +1, ii+1 + +1 + jj-2 = -2 = kk, which is assumed true, which is assumed true

35. 3535
We are skipping…We are skipping…
The well-ordering propertyThe well-ordering property
Why mathematical induction is validWhy mathematical induction is valid
These are the last two sub-sections of These are the last two sub-sections of
section 3.3section 3.3

36. 3636
Question 40Question 40
Take a pile of Take a pile of nn stones stones

Split the pile into two smaller piles of size Split the pile into two smaller piles of size rr
and and ss

Repeat until you have Repeat until you have nn piles of 1 stone each piles of 1 stone each
Take the product of Take the product of allall the splits the splits

So all the So all the rr’s and ’s and ss’s from ’s from each each splitsplit
Sum up each of these productsSum up each of these products
Prove that this product equals Prove that this product equals
2
)1(nn

37. 3737
10
3
14
7
1 12 2 2 1
23
1 1 1 1 1 1
21
12 2
4 2 1
1 1 1
Question 40Question 40
2
)1(nn
10
2
9*10
4511112421221 

38. 3838
Question 40Question 40
We will show it is true for a pile of We will show it is true for a pile of kk
stones, and show it is true for stones, and show it is true for kk+1 stones+1 stones

So P(So P(kk) means that it is true for ) means that it is true for kk stones stones
Base case: Base case: nn = 1 = 1

No splits necessary, so the sum of the No splits necessary, so the sum of the
products = 0products = 0

1*(1-1)/2 = 01*(1-1)/2 = 0

Base case provenBase case proven

39. 3939
Question 40Question 40
Inductive hypothesis: assume that P(1), P(2), …, Inductive hypothesis: assume that P(1), P(2), …,
P(P(kk) are all true) are all true

This is strong induction!This is strong induction!
Inductive step: Show that P(Inductive step: Show that P(kk+1) is true+1) is true

We assume that we split the We assume that we split the kk+1 pile into a pile of +1 pile into a pile of ii
stones and a pile of stones and a pile of kk+1-+1-ii stones stones

Thus, we want to show that Thus, we want to show that
((ii)*()*(kk+1-+1-ii) + P() + P(ii) + P() + P(kk+1-+1-ii) = P() = P(kk+1)+1)

Since 0 < Since 0 < ii < < k+1k+1, both , both ii and and kk+1-+1-ii are between 1 and are between 1 and
kk, inclusive, inclusive

40. 4040
Question 40Question 40
kkkk 
22
kkiikikkiiiiki 
22222
2222
22
2
2
2222
2 kkiikikkii
iiki






)1P()1P()P()1(*)(  kikiiki
22
)11)(1(
)1P(
2
kkkk
k




2
2
2
)11)(1(
)1P(
22
iikikkikik
ik




2
)P(
2
ii
i



Thus, we want to show that Thus, we want to show that
((ii)*()*(kk+1-+1-ii) + P() + P(ii) + P() + P(kk+1-+1-ii) = P() = P(kk+1)+1)

41. 41
Quick surveyQuick survey

I felt I understood the material in this slide set…I felt I understood the material in this slide set…
a)a)Very wellVery well
b)b)With some review, I’ll be goodWith some review, I’ll be good
c)c)Not reallyNot really
d)d)Not at allNot at all

42. 42
Quick surveyQuick survey

The pace of the lecture for this slide set was…The pace of the lecture for this slide set was…
a)a)FastFast
b)b)About rightAbout right
c)c)A little slowA little slow
d)d)Too slowToo slow

43. 43
Quick surveyQuick survey

How interesting was the material in this slide How interesting was the material in this slide
set? Be honest!set? Be honest!
a)a)Wow! That was SOOOOOO cool!Wow! That was SOOOOOO cool!
b)b)Somewhat interestingSomewhat interesting
c)c)Rather bortingRather borting
d)d)ZzzzzzzzzzzZzzzzzzzzzz