Mathematical Induction - Stanford University

1 Mathematical Induction Everybody do the wave! The Wave If done properly, everyone will eventually end up joining in. Why is that? Someone (me!) started everyone off. Once the person before you did the wave, you did the wave. The principle of Mathematical Induction states that if for some P(n) the following hold:P(0) is trueandFor any n , we have P(n) P(n + 1)thenFor any n , P(n) is it starts it stays it's always true. Induction , Intuitively It's true for 0. Since it's true for 0, it's true for 1. Since it's true for 1, it's true for 2. Since it's true for 2, it's true for 3. Since it's true for 3, it's true for 4. Since it's true for 4, it's true for 5. Since it's true for 5, it's true for 6.

2 Proof by Induction Suppose that you want to prove that some property P(n) holds of all natural numbers. To do so: Prove that P(0) is true. This is called the basis or the base case. Prove that for all n , that if P(n) is true, then P(n + 1) is true as well. This is called the inductive step. P(n) is called the inductive hypothesis. Conclude by Induction that P(n) holds for all n. Some Summations 20 = 1 = 21 120 + 21 = 1 + 2 = 3 = 22 120 + 21 + 22 = 1 + 2 + 4 = 7 = 23 120 + 21 + 22 + 23 = 1 + 2 + 4 + 8 = 15 = 24 120 + 21 + 22 + 23 + 24 = 1 + 2 + 4 + 8 + 16 = 31 = 25 1 Theorem: The sum of the first n powers of two is 2n 1. Proof: By Induction . Let P(n) be the sum of the first n powersof two is 2n 1.

3 We will show P(n) is true for all n . For our base case, we need to show P(0) is true, meaningthe sum of the first zero powers of two is 20 1. Since thesum of the first zero powers of two is 0 = 20 1, we seeP(0) is true. For the inductive step, assume that for some n that P(n) holds, meaning that 20 + 21 + .. + 2n-1 = 2n 1. We need to show that P(n + 1) holds, meaning that the sumof the first n + 1 powers of two is numbers is 2n+1 1. Consider the sum of the first n + 1 powers of two. This isthe sum of the first n powers of two, plus 2n. Using the inductive hypothesis, we see that 20 + 21 + .. + 2n-1 + 2n = (20 + 21 + .. + 2n-1) + 2n= 2n 1 + 2n= 2(2n) 1= 2n+1 1 Thus P(n + 1) is true, completing the Induction .

4 Just as in a proof by contradiction or contrapositive, we should mention this proof is by as in a proof by contradiction or contrapositive, we should mention this proof is by Induction . Theorem: The sum of the first n powers of two is 2n 1. Proof: By Induction . Let P(n) be the sum of the first n powersof two is 2n 1. We will show P(n) is true for all n . For our base case, we need to show P(0) is true, meaningthe sum of the first zero powers of two is 20 1. Since thesum of the first zero powers of two is 0 = 20 1, we seeP(0) is true. For the inductive step, assume that for some n that P(n) holds, meaning that 20 + 21 + .. + 2n-1 = 2n 1. We need to show that P(n + 1) holds, meaning that the sumof the first n + 1 powers of two is numbers is 2n+1 1.

5 Consider the sum of the first n + 1 powers of two. This isthe sum of the first n powers of two, plus 2n. Using the inductive hypothesis, we see that 20 + 21 + .. + 2n-1 + 2n = (20 + 21 + .. + 2n-1) + 2n= 2n 1 + 2n= 2(2n) 1= 2n+1 1 Thus P(n + 1) is true, completing the Induction . Now, we state what property P(n) we are going to prove holds for all n . Now, we state what property P(n) we are going to prove holds for all n . Theorem: The sum of the first n powers of two is 2n 1. Proof: By Induction . Let P(n) be the sum of the first n powersof two is 2n 1. We will show P(n) is true for all n . For our base case, we need to show P(0) is true, meaningthe sum of the first zero powers of two is 20 1.

6 Since thesum of the first zero powers of two is 0 = 20 1, we seeP(0) is true. For the inductive step, assume that for some n that P(n) holds, meaning that 20 + 21 + .. + 2n-1 = 2n 1. We need to show that P(n + 1) holds, meaning that the sumof the first n + 1 powers of two is numbers is 2n+1 1. Consider the sum of the first n + 1 powers of two. This isthe sum of the first n powers of two, plus 2n. Using the inductive hypothesis, we see that 20 + 21 + .. + 2n-1 + 2n = (20 + 21 + .. + 2n-1) + 2n= 2n 1 + 2n= 2(2n) 1= 2n+1 1 Thus P(n + 1) is true, completing the Induction . The first step of an inductive proof is to show P(0). We explicitly state what P(0) is, then try to prove it.

7 We can prove P(0) using any proof technique we'd first step of an inductive proof is to show P(0). We explicitly state what P(0) is, then try to prove it. We can prove P(0) using any proof technique we'd like. Theorem: The sum of the first n powers of two is 2n 1. Proof: By Induction . Let P(n) be the sum of the first n powersof two is 2n 1. We will show P(n) is true for all n . For our base case, we need to show P(0) is true, meaningthe sum of the first zero powers of two is 20 1. Since thesum of the first zero powers of two is 0 = 20 1, we seeP(0) is true. For the inductive step, assume that for some n that P(n) holds, meaning that 20 + 21 + .. + 2n-1 = 2n 1.

8 We need to show that P(n + 1) holds, meaning that the sumof the first n + 1 powers of two is 2n+1 1. Consider the sum of the first n + 1 powers of two. This isthe sum of the first n powers of two, plus 2n. Using the inductive hypothesis, we see that 20 + 21 + .. + 2n-1 + 2n = (20 + 21 + .. + 2n-1) + 2n= 2n 1 + 2n= 2(2n) 1= 2n+1 1 Thus P(n + 1) is true, completing the Induction . The goal of this step is to prove For any n , if P(n), then P(n + 1) To do this, we'll choose an arbitrary n, assume that P(n) holds, then try to prove P(n + 1).The goal of this step is to prove For any n , if P(n), then P(n + 1) To do this, we'll choose an arbitrary n, assume that P(n) holds, then try to prove P(n + 1).

9 Theorem: The sum of the first n powers of two is 2n 1. Proof: By Induction . Let P(n) be the sum of the first n powersof two is 2n 1. We will show P(n) is true for all n . For our base case, we need to show P(0) is true, meaningthe sum of the first zero powers of two is 20 1. Since thesum of the first zero powers of two is 0 = 20 1, we seeP(0) is true. For the inductive step, assume that for some n that P(n) holds, meaning that 20 + 21 + .. + 2n-1 = 2n 1. We need to show that P(n + 1) holds, meaning that the sumof the first n + 1 powers of two is 2n+1 1. Consider the sum of the first n + 1 powers of two. This isthe sum of the first n powers of two, plus 2n. Using the inductive hypothesis, we see that 20 + 21 +.

10 + 2n-1 + 2n = (20 + 21 + .. + 2n-1) + 2n= 2n 1 + 2n= 2(2n) 1= 2n+1 1 Thus P(n + 1) is true, completing the Induction . Here, we're explicitly stating P(n + 1), which is what we want to prove. Now, we can use any proof technique we want to try to prove , we're explicitly stating P(n + 1), which is what we want to prove. Now, we can use any proof technique we want to try to prove it. Theorem: The sum of the first n powers of two is 2n 1. Proof: By Induction . Let P(n) be the sum of the first n powersof two is 2n 1. We will show P(n) is true for all n . For our base case, we need to show P(0) is true, meaningthe sum of the first zero powers of two is 20 1. Since thesum of the first zero powers of two is 0 = 20 1, we seeP(0) is true.