Proofs by InductionAn Example of InductionThe Induction RuleLike Dominos…Example Induction Proof Proof by InductionExample Induction ProofAn Example ProofAn Example ProofAn Example ProofAn Example ProofAn Aside: EllipsesProblemsThe MIT Stata CenterThe Stata Center PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaThe Gehry/Gates PlazaIngenious Induction HypothesesIngenious Induction HypothesesInductive (Recursive) ProceduresProblemsA False ProofA False ProofA False ProofA False ProofA False ProofA False ProofL2-1.1September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. Proofsby InductionL2-1.2September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. An Example of InductionSuppose we have a property (say color) ofthe natural numbers:0, 1, 2, 3, 4, 5, …Showing that zero is red, and thatthe successor of any red number is red,proves that all numbers are red!L2-1.3September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Induction Rule0 and (from n to n+1)proves 0, 1, 2, 3,….R(0), ∀n∈N [R(n)→R(n+1)]∀m∈N R(m)_____L2-1.4September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. Like Dominos…L2-1.5September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. Example Induction ProofLet’s prove:12111nnrrr rr+−++ + + =−LL2-1.6September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. Proof by InductionStatements in green form a template forinductive proofs:Proof: (by induction on n)The induction hypothesis:12()::111nnrrrP rrn+−++ + + ==−LL2-1.7September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. Example Induction ProofBase Case (n = 0):111rr−==−0120?1111rrr rr+−++ + + =−L14442 4 443Wait: divide by zero bug! This is only true for r ≠ 1L2-1.8September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. An Example ProofRevised Induction Hypothesis:12( 1::11)1nnrrr rrrPn+−++ + + =∀≠−= L 12111nnrrr rr+−++ + + =−LRevised Theorem:r ≠ 1∀L2-1.9September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. An Example ProofInduction Step: Assume P(n) forn ≥ 0 to prove P(n + 1):(1)1121111nnrrrrrr+++−∀≠ + + + + =−LL2-1.10September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. An Example ProofHave P(n) by assumption:Adding r n+1to both sides:12111nnrrr rr+−++ + + =−L111111111(1)1nnn nnnrrr rrrrrr+++++−+++ = +−−+ −=−LL2-1.11September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. An Example ProofContinued…Which is just P(n+1)Therefore theorem is true by induction. QED.1111(1)111111nnnnnnrrrrrrrrr++++++−+ ⋅ +−+++ =−−=−LL2-1.12September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. An Aside: EllipsesEllipses (…) mean that the reader issupposed to infer a pattern.• Can lead to confusion • Summation notation gives more precision, for example:021nniirr r r=++ + + =∑LL2-1.13September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. Class Problem 1ProblemsL2-1.14September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The MIT Stata CenterCopyright © 2003, 2004, 2005 Norman Walsh. This work is licensed under a Creative Commons License.L2-1.15September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Stata Center PlazaL2-1.16September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005.The Gehry/Gates PlazaGoal: tile the squares, except one in the middle for Bill. n2n2Photo courtesy of Ricardo Stuckert/ABr.L2-1.17September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005.The Gehry/Gates PlazaGehry specifies L-shaped tiles covering three squares:For example, for 8 x 8 plaza might tile for Bill this way:Photo courtesy of Ricardo Stuckert/ABr.L2-1.18September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaTheorem: For any 2n× 2n plaza, we can make Bill and Frank happy.Proof: (by induction on n)P(n) ::= can tile 2n× 2nwith Bill in middle.Base case: (n=0)(no tiles needed)Photo courtesy of Ricardo Stuckert/ABr.L2-1.19September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates Plazan2Induction step: assume can tile 2n × 2n,prove can handle 2n+1× 2n+1.12+nPhoto courtesy of Ricardo Stuckert/ABr.L2-1.20September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaNow what?12+nn2Photo courtesy of Ricardo Stuckert/ABr.L2-1.21September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaThe fix:Prove that we can always finda tiling with Bill in the corner.L2-1.22September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaNote: Once have Bill in corner,can get Bill in middle:Photo courtesy of Ricardo Stuckert/ABr.L2-1.23September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaMethod: Rotate the squares as indicated.Photo courtesy of Ricardo Stuckert/ABr.L2-1.24September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaMethod: after rotation have:Photo courtesy of Ricardo Stuckert/ABr.L2-1.25September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaMethod: Now group the 4 squares together,and insert a tile.Done!Bill inmiddlePhoto courtesy of Ricardo Stuckert/ABr.L2-1.26September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaTheorem: For any 2n× 2n plaza, we can put Bill in the corner.Proof: (by induction on n)P(n) ::= can tile 2n× 2nwith Bill in cornerBase case: (n=0)(no tiles needed)Photo courtesy of Ricardo Stuckert/ABr.L2-1.27September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005.The Gehry/Gates PlazaInduction step:Assume we can get Bill in corner of 2n× 2n.Prove we can get Bill in corner of 2n+1× 2n+1.n2n2Photo courtesy of Ricardo Stuckert/ABr.L2-1.28September 21, 2005Copyright © Albert R. Meyer and Ronitt Rubinfeld, 2005. The Gehry/Gates PlazaMethod: Rotate the squares as indicated.Photo courtesy of Ricardo Stuckert/ABr.L2-1.29September 21,
View Full Document
Unlocking...