# тйњу║│

ТюгуФаСИ╗УдЂтГдС╣аТЋ░тГдСИГУ┐љућеуџётйњу║│Т│Ћсђѓтйњу║│тюеТЋ░тГдСИГТюЅуЮђжЮътИИжЄЇУдЂуџёСйюућесђѓТюгТќЄСИЙСЙІУ»┤ТўјС║єтѕЕућетйњу║│ТЮЦУ»ЂТўјУ«║жбўуџёТќ╣Т│Ћсђѓжђџтйњу║│У»ЂТўјТеАТЮ┐ТЏ┤тЦйуџётГдС╣аС║єтйњу║│Т│Ћсђѓ
т▒Ћт╝ђТЪЦуюІУ»дТЃЁ

1.Induction 2/24/12 1

2.The Idea of Induction Color the integers РЅЦ 0 0 , 1 , 2 , 3 , 4 , 5 , Рђд I tell you, 0 is red , &amp; any int next to a red integer is red , then you know that all the ints are red ! 2/24/12 2

3.Induction Rule 2/24/12 3

4.Like DominosРђд

5.Example Induction Proof LetРђЎs prove: (for r РЅа 1)

6.Statements in magenta form a template for inductive proofs: Proof: (by induction on n ) The induction hypothesis, P ( n ) , is: Example Induction Proof (for r РЅа 1)

7.Base Case ( n = 0 ) : Example Induction Proof 1 OK!

8.Inductive Step: Assume P ( n ) for some n РЅЦ 0 and prove P ( n+1 ) : Example Induction Proof

9.Now from induction hypothesis P ( n ) we have Example Induction Proof so add r n+1 to both sides

10.adding r n+1 to both sides, Example Induction Proof This proves P ( n+1 ) completing the proof by induction.

11.Рђю №Ђї РђЮ is an ellipsis . Can lead to confusion (n = 0 ?) Sum notation more precise Means you should see a pattern : an aside: ellipsis

ТѕЉт░▒Тў»ТѕЉ№╝Ђ
ти▓т░єжЊЙТјЦтцЇтѕХУЄ│тЅфУ┤┤ТЮ┐