Hopefully, you were able to discover that the minimum number of moves will always be 2n - 1, where n is the number of washers. Even though this seems to be the pattern in the table, for mathematicians to consider this a legitimate result, there must be some type of proof; finding a pattern is just not enough. This is where mathematical induction comes in. Mathematical Induction is a method of proving theorems about positive integers. There are three parts to an induction proof: . The Basis: We must show that the theorem is true when the variable equals 1. . The Inductive Hypothesis: We assume that the theorem is true for n (or k, depending on the variable given in the problem). o The Inductive Step: We must show that the theorem is true for n+1 (or k+1), given the fact that it is true for n (or k). The first two parts of the proof are generally short and are not difficult to establish. The third part requires a little more thought. Watch this excellent 7-minute video: x+Y:? Proof by Mathematical Induction - How to doAL INDUCTION Watch later Share NE 1+2+ 3+ ... the n(1+1 ) 2 BASIS: n= 1 1=1 V K(K+ VDUCTION: ASSUME TRUE ACK 1+2+3+.+KS 2 SHOW TRUE 1+ 2 + 3 + ...+ K + K+1 = ( 1 + 1 ) EXPO Low16507 Watch on Youtube Check out the examples in this video to get some practice proving using mathematical induction. Pause the video and see if you can finish the step. Have fun! Viathematical Share InductionNow that you've practiced, try out these examples to master the objective. Example 1 Let's practice an induction proof by proving the result that we found for the Tower of Hanoi problem. We will show that the minimum number of moves needed to move n washers from one peg to another is 2n - 1. Solution The Basis: If there is only one washer, then obviously it will only take one move to get the washer to another peg. The theorem reinforces this since 21-1=1. The Inductive Hypothesis: Now, let's assume that the minimum number of moves needed to move n = k washers is 2k - 1. (Remember, right now, we're not sure of this rule for any number except 1. This is why we need the inductive step.) The Inductive Step: Suppose now that we have k+1 washers. In order to get down to the bottom washer, we must first move the n washers that are on top of it. By our hypothesis, this will take 2k - 1 moves. Once this is done, it will take one move to get the bottom washer to another peg. Finally, it will take 2k - 1 moves again to move the n washers back on top of the bottom washer. So, counting our sequence of moves we have (2% -1)+1+(2* -1) = 22" -1)+1 =2:2%-2+1 =2 -1 This agrees with the formula that we are trying to prove, so we're finished! Let's take one more look at what we've accomplished. The basis says the theorem is true for 1 washer. The inductive step says that if the theorem is true for 1, then it must be true for 2, but if it's true for 2, it must be true for 3, but if it's true for 3, then it must be true for 4, etc. The idea on ALL STEPS is to work on each side separately until you finish simplifying and the last line checks Example 2 Prove that 1 + 3 + 5 +...+ (2n - 1) = n? for all positive integers n. Solution: The Basis: Ifn=1,then 2(1)-1=12 2-1 =1 1= 1 So, the theorem holds for n=1. The Inductive Hypothesis: Assume that n=k. In other words, assume that Example 2 Prove that 1 + 3 + 5 +...+ (2n - 1) = n? for all positive integers n. Solution: The Basis: Ifn=1, then 2(1)-1=12 2-1 =1 1= 1 So, the theorem holds for n = 1. The Inductive Hypothesis: Assume that n = k. In other words, assume that 1+3+5+.+(2k-1) =k?is true. The Inductive Step: Consider k + 1. We need to show that 1+3+5+.+(2k - 1) + (2(k+1) - 1) = (k+1)2. To show that this statement is true, we will start by adding 2(k+1) - 1 (the next term of the sequence) to both sides of the equation we have written in our hypothesis: 1+3+5+.+(2k-1) +2(k+1) - 1=k?+2(k+1) - 1 Now, we just simplify the right hand side. 1+3+5+.+(2k-1) +2(k+1)-1=k2+2(k+1)- 1 =k2+2k+2-1 =k2+2k+1 =(k+1)? Thus, we have just shown that 1 + 3+ 5 +..+ (2k - 1) + (2(k+1) - 1) = (k+1)%, which proves our theorem. One tricky thing about induction proofs is that they are all different. You always need to follow this basic three-step format, but the methods you'll need to use to prove the theorems, particularly for the inductive step, will often be very different. Summary The Basis: Requirements: Assumption and substitution on right and left, followed by simplifying on both sides: Summary The Basis: Requirements: Assumption and substitution on right and left, followed by simplifying on both sides: #1in the Assignment should look like this: Assume n=1: 1=(1*(1+1))/2 1=2/2 1=1 @ The Inductive Hypothesis: Requirements: Assumption and ALL of problems' info on the left. #1in the Assignment should look like this: Assume n=k: 1+2+....+k = (k(k+1))/2 The Inductive Step: Requirements: Assumption ,ALL of problems info on the left. ,and simplify each side separately with the goal that the last info on each side matches. #3 1st step should look like this: Assume n=k+1: 2+4+6+..+ 2k + 2(k+1) = (k+1)2+ (k+1) Here's one for you to try on your own. 2 _a(r+D)(2z+1) 6 Provethat 1 +2% +3% +__+ Mathematical induction can also be used to prove divisibility. Example 3 Prove that 4" - 1 is evenly divisible by 3 for all positive integers n. Solution Example 3 Prove that 4" - 1 is evenly divisible by 3 for all positive integers n. Solution The Basis: If n=1,then 4!- 1= 3. Since 3is evenly divisible by 3 the theorem holds for n = 1. The Inductive Hypothesis: Assume thatn =k. In other words, assume that 4 - 1 is evenly divisible by 3. The Inductive Step: Consider k + 1. We need to show that 4%*1 - 1 is evenly divisible by 3 for all integers k. Notice that 4k*1- 1 = 4(4K) - 1 = 4(4%) - 4 + 4 - 1= 4(4%- 1) + 3. From our hypothesis, 4 - 1 is divisible by 3. Since 3 is also divisible by 3, 4(4% - 1) + 3 is a sum of two numbers that are divisible by 3, which means that the sum is also divisible by 3. Thus, 4