Mathematical Induction CS 202 Epp chapter 4 Aaron Bloomfield 1 How do you climb infinite stairs Not a rhetorical question First you get to the base platform of the staircase Then repeat From your current position move one step up 2 Let s use that as a proof method First show P x is true for x 0 This is the base of the stairs Then show that if it s true for some value n then it is true for n 1 Show P n P n 1 This is climbing the stairs Let n 0 Since it s true for P 0 base case it s true for n 1 Let n 1 Since it s true for P 1 previous bullet it s true for n 2 Let n 2 Since it s true for P 2 previous bullet it s true for n 3 Let n 3 And onwards to infinity Thus we have shown it to be true for all non negative numbers 3 What is induction A method of proof It does not generate answers it only can prove them Three parts Base case s show it is true for one element get to the stair s base platform Inductive hypothesis assume it is true for any given element assume you are on a stair Must be clearly labeled Show that if it true for the next highest element show you can move to the next stair 4 Induction example Show that the sum of the first n odd integers is n2 Example If n 5 1 3 5 7 9 25 52 Formally show n n P n where P n 2 2 i 1 n i 1 Base case Show that P 1 is true 1 P 1 2 i 1 12 i 1 1 1 5 Induction example continued Inductive hypothesis assume true for k Thus we assume that P k is true or that k 2 2 i 1 k i 1 Note we don t yet know if this is true or not Inductive step show true for k 1 We want to show that k 1 2 2 i 1 k 1 i 1 6 Induction example continued k Recall the inductive hypothesis 2i 1 k 2 i 1 Proof of inductive step k 1 2 2 i 1 k 1 i 1 k 2 k 1 1 2i 1 k 2 2k 1 i 1 2 k 1 1 k 2 k 2 2k 1 k 2 2k 1 k 2 2k 1 7 What did we show Base case P 1 If P k was true then P k 1 is true i e P k P k 1 We know it s true for P 1 Because of P k P k 1 if it s true for P 1 then it s true for P 2 Because of P k P k 1 if it s true for P 2 then it s true for P 3 Because of P k P k 1 if it s true for P 3 then it s true for P 4 Because of P k P k 1 if it s true for P 4 then it s true for P 5 And onwards to infinity Thus it is true for all possible values of n In other words we showed that P 1 k P k P k 1 n P n 8 The idea behind inductive proofs Show the base case Show the inductive hypothesis Manipulate the inductive step so that you can substitute in part of the inductive hypothesis Show the inductive step 9 Second induction example Show the sum of the first n positive even integers is n2 n Rephrased n n P n where P n 2i n 2 n The three parts i 1 Base case Inductive hypothesis Inductive step 10 Second induction example continued Base case Show P 1 1 P 1 2 i 12 1 i 1 2 2 Inductive hypothesis Assume k P k 2i k 2 k i 1 Inductive step Show k 1 P k 1 2i k 1 2 k 1 i 1 11 Second induction example continued Recall our inductive hypothesis k P k 2i k 2 k i 1 k 1 2 2 i k 1 k 1 i 1 k 2 k 1 2i k 1 2 k 1 i 1 2 k 1 k 2 k k 1 2 k 1 k 2 3k 2 k 2 3k 2 12 Notes on proofs by induction We manipulate the k 1 case to make part of it look like the k case We then replace that part with the other side of the k case k k 1 2 2 i k 1 k 1 P k 2i k 2 k i 1 i 1 k 2 k 1 2i k 1 2 k 1 i 1 2 k 1 k 2 k k 1 2 k 1 k 2 3k 2 k 2 3k 2 13 Third induction example Show n n 1 2n 1 i 6 i 1 n 2 Base case n 1 1 1 1 2 1 i 6 i 1 6 2 1 6 1 1 1 2 Inductive hypothesis assume k k 1 2k 1 i 6 i 1 k 2 14 Third induction example Inductive step show k 1 k 1 k 1 k 1 1 2 k 1 1 i 6 i 1 2 k 1 k 1 1 2 k 1 1 i 6 i 1 2 k 1 k 2 2k 3 k 1 i 6 i 1 2 k 2 k k 1 2k 1 k 1 k 2 2k 3 k 1 6 6 2 6 k 1 2 k k 1 2k 1 k 1 k 2 2k 3 k 2k 9k 13k 6 2k 9k 13k 6 i 2 3 2 3 2 i 1 k k 1 2k 1 15 6 Third induction again what if your inductive hypothesis was wrong Show i 2 n n 1 2n 2 6 n i 1 Base case n 1 1 1 1 2 2 2 i 6 i 1 7 2 1 6 7 1 6 1 But let s continue anyway Inductive hypothesis assume k k k 1 2k 2 i 6 i 1 2 16 Third induction again what if your inductive hypothesis was wrong Inductive step show k 1 k 1 k 1 k 1 1 2 k 1 2 i 6 i 1 2 k 1 k 1 1 2 k 1 2 i 6 i 1 2 k 1 k 2 2k 4 k 1 i 6 i 1 2 k 2 k k 1 2k 2 k 1 k 2 2k 4 k 1 6 6 2 6 k 1 2 k k 1 2k 2 k 1 k 2 2k 4 k 2k 10k 14k 6 2k 10k 16k 8 i 2 3 2 3 2 i 1 k k 1 2k 2 17 6 Fourth induction example S that n nn for all n 1 Base case n 2 2 22 …