Mathematical Induction Proof Techniques Explained

Proof by Induction Proof by Induction Twitter: @Owen134866 www.mathsfreeresourcelibrary.com

Prior Knowledge Check ? 2 1) Write down expressions for: 3) ? = ? =5 3 and ? + 1 8 2 0 ? ? + 1 a) ? ? = 1 b) ?2 ? = 1 Find ?? in terms of ?. ? ??(?+ ?) ? ?(? + ?)(? + ?)(?? + ?) ?? ? ?? ?? ?? ?? + ? 2) Prove that for all positive integers n, 3?+2 3? is divisible by 8.

Teachings for Teachings for Exercise 8A Exercise 8A

Proof by Induction How this works mathematically You can obtain a proof for the summation of a series, by using the induction method BASIS Show that the statement to be proven works for the case n = 1 The way proof by mathematical induction works is often likened to knocking dominoes over ASSUMPTION Assume that the statement is true for n = k (just replace the ns with ks!) If the dominoes are lined up, then you knock over the first one, every domino afterwards will fall down iPhone Dominoes INDUCTIVE Show that if the statement is true for n = k, it is also true for n = k + 1 (ie the next case) This is harder to explain without an example. Essentially you find a way to express the next case using k and show that it is equivalent to replacing k with k + 1 Mathematically, if we want to prove that something is true for all possible cases, we cannot do it numerically (as the numbers would just go on forever) CONCLUSION You have shown that if the statement is true for one case, it must be true for the next However, if we show that if one case is true, and so is the next case, then we can therefore show it is true for every case As it was true for n = 1, it must therefore be true for n = 2, 3, 4 and so on, PROVING the statement! 8A

Proof by Induction You can obtain a proof for the summation of a series, by using the induction method We will start by proving statements relating to the sum of a series. Prove by mathematical induction that, for ? + This means n can be any positive integer ? 2? 1 = ?2 ?=1 This is the formula for the sequence This is the formula for the sum of the first n terms of the sequence So we need to use the steps from before to prove this statement 8A

Proof by Induction BASIS Show that the statement is true for n = 1 You can obtain a proof for the summation of a series, by using the induction method ? 2? 1 = ?2 We will start by proving statements relating to the sum of a series. ?=1 Replace n with 1 Replace n with 1 Prove by mathematical induction that, for ? + ? 1 2? 1 = ?2 There will only be one term here, that we get by subbing n = 1 into the expression (1)2 2? 1 Calculate ?=1 ?=1 So we need to use the steps from before to prove this statement = 1 = 1 The statement given is therefore true for n = 1 BASIS ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction ASSUMPTION Assume the statement is true for n = k ? 2? 1 = ?2 You can obtain a proof for the summation of a series, by using the induction method We will start by proving statements relating to the sum of a series. ?=1 ? 2? 1 = 1 + 3 + 5 + 7 + 9 +....+ (2? 1) = ?2 Prove by mathematical induction that, for ? + ?=1 ? 2? 1 = ?2 Write out the first few terms in the sequence, and the last term, which will be in terms of k We are going to assume that this sequence is true for k, and hence the sum will be equal to k2 ?=1 So we need to use the steps from before to prove this statement BASIS ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction ASSUMPTION Assume the statement is true for n = k ? 2? 1 = ?2 You can obtain a proof for the summation of a series, by using the induction method We will start by proving statements relating to the sum of a series. ?=1 ? 2? 1 = 1 + 3 + 5 + 7 + 9 +....+ (2? 1) = ?2 Prove by mathematical induction that, for ? + ?=1 INDUCTIVE Show the statement is then true for (k + 1) ie) The next term (sub in (k + 1)) for it! ? 2? 1 = ?2 The sequence will be the same, but with an extra term ?=1 ?+1 So we need to use the steps from before to prove this statement 2? 1 = 1 + 3 + 5 + 7 + 9 +....+ 2? 1 + (2 ? + 1 1) ?=1 = 1 + 3 + 5 + 7 + 9 +....+ 2? 1 + (2? + 1) BASIS You can replace the first part as we assumed it was equal to k2 earlier ASSUMPTION INDUCTIVE CONCLUSION = ?2+ (2? + 1) = ? + 12 8A

Proof by Induction CONCLUSION You can obtain a proof for the summation of a series, by using the induction method ? 2? 1 = ?2 ?=1 ? ?+1 We will start by proving statements relating to the sum of a series. 2? 1 =?2 2? 1 =(? + 1)2 ?=1 ?=1 We assumed that for n = k, the sum of the series would be equal to k2 Using this assumption, we showed that the summation for (k + 1) is equal to (k + 1)2 Prove by mathematical induction that, for ? + ? 2? 1 = ?2 So if the statement is true for one value, it will therefore be true for the next value ?=1 As it is true for the next value, it will therefore be true for the value after that, and so on So we need to use the steps from before to prove this statement However, this all relies on the assumption being correct BASIS Remember for the BASIS step, we showed that the statement is true for n = 1? ASSUMPTION INDUCTIVE CONCLUSION Well because it is true for n = 1, it must therefore be true for n = 2, n = 3 and so on! The statement is therefore true for all values of n! 8A

Proof by Induction BASIS Show that the statement is true for n = 1 You can obtain a proof for the summation of a series, by using the induction method ? ?2=1 6? ? + 1 2? + 1 ?=1 Prove, by mathematical induction, that for ? +, Replace n with 1 Replace n with 1 ? ?2=1 1 6? ? + 1 2? + 1 There will only be one term here, that we get by subbing n = 1 into the expression 1 6(1) 1 + 1 2 + 1 ?2 ?=1 ?=1 Calculate So we are now going to prove one of the formulae you have learnt in chapter 5! = 1 = 1 The statement given is therefore true for n = 1 BASIS ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can obtain a proof for the summation of a series, by using the induction method ? 1 6? ? + 1 2? + 1 ?2= 1 + 4 + 9 + 16 + ?2 = Prove, by mathematical induction, that for ? +, ?=1 ? ?2=1 6? ? + 1 2? + 1 Write out the first few terms in the sequence, and the last term, which will be in terms of k We are going to assume that this sequence is true for k, and hence the sum will be equal to the expression above ?=1 So we are now going to prove one of the formulae you have learnt in chapter 5! BASIS ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can obtain a proof for the summation of a series, by using the induction method ? 1 6? ? + 1 2? + 1 ?2= 1 + 4 + 9 + 16 + ?2= Prove, by mathematical induction, that for ? +, ?=1 INDUCTIVE Show the statement is then true for (k + 1) ie) The next term The sequence will be the same, but with an extra term (sub in (k + 1)) for it! ? ?2=1 6? ? + 1 2? + 1 ?=1 ?+1 ?2= 1 + 4 + 9 + 16 + ?2 + (? + 1)2 So we are now going to prove one of the formulae you have learnt in chapter 5! ?=1 Replace the first part with the assumed formula from earlier! 1 6? ? + 1 2? + 1 + (? + 1)2 BASIS = ASSUMPTION INDUCTIVE CONCLUSION This requires more simplification which will be shown on the next slide!! 8A

Proof by Induction INDUCTIVE Show the statement is then true for (k + 1) ie) The next term The sequence will be the same, but with an extra term (sub in (k + 1)) for it! You can obtain a proof for the summation of a series, by using the induction method ?+1 ?2= 1 + 4 + 9 + 16 + ?2 + (? + 1)2 Prove, by mathematical induction, that for ? +, ?=1 Replace the first part with the assumed formula from earlier! ? ?2=1 1 6? ? + 1 2? + 1 + (? + 1)2 6? ? + 1 2? + 1 = Rewrite both as fractions over 6 ?=1 + 6 ? + 12 ? ? + 1 2? + 1 6 = 6 So we are now going to prove one of the formulae you have learnt in chapter 5! Combine ? ? + 1 2? + 1 + 6(? + 1)2 6 [ = Clever factorisation method! ] BASIS (? + 1) ?(2? + 1) + 6(? + 1) = ASSUMPTION INDUCTIVE CONCLUSION 6 Expand and simplify the inner brackets (? + 1) 2?2+ 7? + 6 [ ] = 6 Factorise the inner part (? + 1)(? + 2)(2? + 3) = 6 6A 8A

Proof by Induction CONCLUSION Explain why it proves the original statement You can obtain a proof for the summation of a series, by using the induction method For n = k For n = (k + 1) Prove, by mathematical induction, that for ? +, 1 6? ? + 1 2? + 1 1 6(? + 1) ? + 2 2? + 3 = = ? Rewrite some of the brackets ?2=1 6? ? + 1 2? + 1 ?=1 1 6(? + 1) ? + 1 + 1 2(? + 1) + 1 = So we are now going to prove one of the formulae you have learnt in chapter 5! Written in this way, you can see that the k s in the first statement have all been replaced with k + 1 s BASIS So the statement was true for n = 1 ASSUMPTION INDUCTIVE CONCLUSION We also showed that if it is true for one statement, it is true for the next Therefore the formula has been proven! 8A

Proof by Induction BASIS Show that the statement is true for n = 1 You can obtain a proof for the summation of a series, by using the induction method ? ?2?= 2 1 + (? 1)2? Prove, by mathematical induction, that for ? +, ?=1 Replace n with 1 Replace n with 1 ? ?2?= 2 1 + (? 1)2? 1 There will only be one term here, that we get by subbing n = 1 into the expression ?2? ?=1 2 1 + (1 1)21 ?=1 Calculate This looks more complicated, but you just follow the same process as you have seen already! = 2 = 2 BASIS The statement given is therefore true for n = 1 ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can obtain a proof for the summation of a series, by using the induction method ? ?2?= 2 + 8 + 24 + 64 + ?(2?) = 2 1 + ? 1 2? Prove, by mathematical induction, that for ? +, ?=1 ? ?2?= 2 1 + (? 1)2? We are going to assume that this sequence is true for k, and hence the sum will be equal to the expression above Write out the first few terms in the sequence, and the last term, which will be in terms of k ?=1 This looks more complicated, but you just follow the same process as you have seen already! BASIS ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can obtain a proof for the summation of a series, by using the induction method ? ?2?= 2 + 8 + 24 + 64 + ?(2?) = 2 1 + ? 1 2? Prove, by mathematical induction, that for ? +, ?=1 INDUCTIVE Show the statement is then true for (k + 1) ie) The next term The sequence will be the same, but with an extra term (sub in (k + 1)) for it! ? ?2?= 2 1 + (? 1)2? ?=1 This looks more complicated, but you just follow the same process as you have seen already! ? ?2?= 2 + 8 + 24 + 64 + ?(2?)+ (? + 1)2?+1 ?=1 Replace the first part with the assumed formula from earlier! BASIS + (? + 1)2?+1 = 2 1 + ? 1 2? ASSUMPTION INDUCTIVE CONCLUSION = 2 + 2(? 1)2?+ (? + 1)2?+1 The simplification for this is difficult You need to aim for the power of 2 to be k + 1 (as it was k originally) 8A

Proof by Induction INDUCTIVE Show the statement is then true for (k + 1) ie) The next term You can obtain a proof for the summation of a series, by using the induction method = 2 + 2(? 1)2?+ (? + 1)2?+1 2 x 2k = 2k+1 (add the powers) Prove, by mathematical induction, that for ? +, = 2 + (? 1)2?+1+ (? + 1)2?+1 In total, we have (k 1) + (k + 1) 2k+1s ? ?2?= 2 1 + (? 1)2? = 2 + (? 1 + ? + 1)2?+1 ?=1 Simplify the bracket This looks more complicated, but you just follow the same process as you have seen already! = 2 + 2?2?+1 Re-factorise the bracket = 2(1 + ?2?+1) BASIS ASSUMPTION INDUCTIVE CONCLUSION 8A

Proof by Induction CONCLUSION Explain why this shows the statement is true You can obtain a proof for the summation of a series, by using the induction method For n = k For n = (k + 1) Prove, by mathematical induction, that for ? +, 2 1 + ? 1 2? 2(1 + ?2?+1) ? Rewrite the first k as k + 1 1 ?2?= 2 1 + (? 1)2? ?=1 2(1 + (? + 1 1)2?+1) This looks more complicated, but you just follow the same process as you have seen already! Written in this way, you can see that the k s in the first statement have all been replaced with k + 1 s So the statement was true for n = 1 BASIS We also showed that if it is true for one statement, it is true for the next ASSUMPTION INDUCTIVE CONCLUSION Therefore the formula has been proven! You will need to become familiar with manipulating powers in the way shown here! 6A 8A

Teachings for Teachings for Exercise 8B Exercise 8B

Proof by Induction BASIS Show that the statement is true for n = 1 You can use proof by induction to prove that an expression is divisible by a given integer ? ? = 32?+ 11 Sub in n = 1 Prove, by induction, that 32n + 11 is divisible by 4 for all positive integers ? + ? 1 = 32(1)+ 11 Calculate = 20 20 is divisible by 4, so the statement is true for n = 1 You follow the same steps as before! BASIS ASSUMPTION INDUCTIVE CONCLUSION 8B

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can use proof by induction to prove that an expression is divisible by a given integer ?? ????????? ?? 4 ??? ? + ? ? = 32?+ 11 INDUCTIVE Show that the statement is then true for n = (k + 1) Prove, by induction, that 32n + 11 is divisible by 4 for all positive integers ? + ? ? + 1 = 32(?+1)+ 11 Multiply out the bracket 32k+2 = 32k x 32 (adding powers when multiplying) So we have 9 lots of 32k You follow the same steps as before! ? ? + 1 = 32?+2+ 11 ? ? + 1 = 32? 32+ 11 BASIS ASSUMPTION INDUCTIVE CONCLUSION ? ? + 1 = 9(32?) + 11 At this point we will combine the expressions for f(k) and f(k + 1) in order to prove that the statement is always divisible by 4 8B

Proof by Induction INDUCTIVE Show that the statement is then true for n = (k + 1) You can use proof by induction to prove that an expression is divisible by a given integer ? ? = 32?+ 11 ? ? + 1 = 9(32?) + 11 Subtract f(k) from f(k + 1), using the expressions above Prove, by induction, that 32n + 11 is divisible by 4 for all positive integers ? + 9 32?+ 11 32?+ 11 ? ? + 1 ?(?) = Group terms on the right side You follow the same steps as before! ? ? + 1 ?(?) = 8(32?) Take out 4 as a factor ? ? + 1 ?(?) = 4 2(32?) BASIS Add f(k) ASSUMPTION INDUCTIVE CONCLUSION ? ? + 1 = ? ? + 4 2(32?) This shows that f(k + 1) is just f(k) with an expression added on CONCLUSION We assumed f(k) was divisible by 4 The expression to be added is divisible by 4 So the answer must be divisible by 4, if f(k) is! As the first case (n = 1) was divisible by 4, the statement must be true! 8B

Proof by Induction BASIS Show that the statement is true for n = 1 You can use proof by induction to prove that an expression is divisible by a given integer ? ? = ?3 7? + 9 Sub in n = 1 Prove, by induction, that the expression n3 7n + 9 is divisible by 3 for all positive integers ? + ? 1 = (1)3 7(1) + 9 Calculate = 3 3 is divisible by 3, so the statement is true for n = 1 BASIS ASSUMPTION INDUCTIVE CONCLUSION 8B

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can use proof by induction to prove that an expression is divisible by a given integer ? ? = ?3 7? + 9 ?? ????????? ?? 3 ??? ? + INDUCTIVE Show that the statement is then true for n = (k + 1) Prove, by induction, that the expression n3 7n + 9 is divisible by 3 for all positive integers ? + ? ? + 1 = (? + 1)3 7(? + 1) + 9 Multiply out the brackets BASIS ? ? + 1 = ?3+ 3?2+ 3? + 1 7? 7 + 9 Group up terms ASSUMPTION INDUCTIVE CONCLUSION ? ? + 1 = ?3+ 3?2 4? + 3 8B

Proof by Induction INDUCTIVE Show that the statement is then true for n = (k + 1) You can use proof by induction to prove that an expression is divisible by a given integer ? ? = ?3 7? + 9 ? ? + 1 = ?3+ 3?2 4? + 3 Subtract f(k) from f(k + 1), using the expressions above Prove, by induction, that the expression n3 7n + 9 is divisible by 3 for all positive integers ? + ?3+ 3?2 4? + 3 ?3 7? + 9 ? ? + 1 ? ? = Multiply by the bracket ? ? + 1 ? ? = ?3+ 3?2 4? + 3 ?3+ 7? 9 Group terms BASIS ? ? + 1 ? ? = 3?2+ 3? 6 ASSUMPTION INDUCTIVE CONCLUSION Take out 3 as a factor ? ? + 1 ? ? = 3(?2+ ? 2) Add f(k) ? ? + 1 = ? ? + 3(?2+ ? 2) This shows that f(k + 1) is just f(k) with an expression added on CONCLUSION We assumed f(k) was divisible by 3 The expression to be added is divisible by 3 So the answer must be divisible by 3, if f(k) is! As the first case (n = 1) was divisible by 3, the statement must be true! 8B

Proof by Induction BASIS Show that the statement is true for n = 1 You can use proof by induction to prove that an expression is divisible by a given integer ? ? = 11?+1+ 122? 1 Sub in n = 1 Prove, by induction, that the expression 11n+1 + 122n-1 is divisible by 133 for all positive integers ? + ? 1 = 112+ 121 Calculate = 133 133 is divisible by 133, so the statement is true for n = 1 This example will require more manipulation as we work through it, but is essentially the same as the previous two BASIS ASSUMPTION INDUCTIVE CONCLUSION 8B

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can use proof by induction to prove that an expression is divisible by a given integer ?? ????????? ?? 133 ??? ? + ? ? = 11?+1+ 122? 1 INDUCTIVE Show that the statement is then true for n = (k + 1) Prove, by induction, that the expression 11n+1 + 122n-1 is divisible by 133 for all positive integers ? + ? ? + 1 = 11(?+1)+1+ 122(?+1) 1 Simplify powers This example will require more manipulation as we work through it, but is essentially the same as the previous two Rewrite ? ? + 1 = 11?+2+ 122?+1 * 11k+2 = 11 x 11k+1 122k+1 = 122 x 122k-1 ? ? + 1 = 11 11?+1+ 122 122? 1 Simplify ? ? + 1 = 11(11?+1) + 144(122? 1) BASIS ASSUMPTION INDUCTIVE CONCLUSION They have been re-written in this way so that, on the next step, the 11s and 12s have the same powers as in the f(k) expression and therefore can be grouped up! * 8B

Proof by Induction INDUCTIVE Show that the statement is then true for n = (k + 1) You can use proof by induction to prove that an expression is divisible by a given integer ? ? = 11?+1+ 122? 1 ? ? + 1 = 11(11?+1) + 144(122? 1) Subtract f(k) from f(k + 1), using the expressions above Prove, by induction, that the expression 11n+1 + 122n-1 is divisible by 133 for all positive integers ? + 11(11?+1) + 144(122? 1) 11?+1+ 122? 1 ? ? + 1 ? ? = Group terms ? ? + 1 ? ? = 10(11?+1) + 143(122? 1) Split the 143 into 2 parts The first 2 terms are just 10 lots of f(k) This example will require more manipulation as we work through it, but is essentially the same as the previous two ? ? + 1 ? ? = 10 11?+1+ 10 122? 1+ 133 122? 1 ? ? + 1 ? ? = 10? ? + 133(122? 1) Add f(k) ? ? + 1 = 11? ? + 133(122? 1) BASIS If f(k) is divisible by 133, so is 11f(k) 133(122k-1) is divisible by 133 Therefore f(k+1) will also be divisible by 133 ASSUMPTION INDUCTIVE CONCLUSION As f(1) was divisible by 133, the statement is therefore true! Make sure you practise enough so you can spot how and when to manipulate in this way! 8B

Teachings for Teachings for Exercise 8C Exercise 8C

Proof by Induction BASIS Show that the statement is true for n = 1 You can use proof by induction to prove general statements involving matrix multiplication ? 1 2? 2? 1 0 1 2 =1 0 Use mathematical induction to prove that: Replace n with 1 Replace n with 1 ? 1 2? 2? 1 0 1 2 =1 ??? ? + 1 0 1 21 21 1 0 1 2 1 0 Calculate Calculate As always, follow the same pattern as with the other induction questions! =1 1 2 =1 1 2 0 0 BASIS So the statement is true for n = 1 ASSUMPTION INDUCTIVE CONCLUSION 8C

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can use proof by induction to prove general statements involving matrix multiplication ? 1 2? 2? 1 0 1 2 =1 ?? ???? ??? ? + 0 Use mathematical induction to prove that: INDUCTIVE Show using the assumption, that the statement will also be true for n = k + 1 ? 1 2? 2? 1 0 1 2 =1 ??? ? + 0 ?1 1 ?+1 =1 1 2 1 2 1 0 1 2 Replace the power k term with the assumed matrix The second matrix doesn t need the power! 0 0 As always, follow the same pattern as with the other induction questions! 1 2? 2? 1 0 1 2 =1 0 BASIS ASSUMPTION INDUCTIVE CONCLUSION Now we need to multiply these matrices using the skills from chapter 4! 8C

Proof by Induction INDUCTIVE Show using the assumption, that the statement will also be true for n = k + 1 You can use proof by induction to prove general statements involving matrix multiplication ?1 1 ?+1 =1 1 2 1 2 1 0 1 2 Replace the power k term with the assumed matrix The second matrix doesn t need the power! Use mathematical induction to prove that: 0 0 1 2? 2? 1 0 1 2 =1 ? 1 2? 2? 1 0 1 2 =1 0 ??? ? + 0 1 1 + ((1 2?) 0) 1 1 + ((1 2?) 2) As always, follow the same pattern as with the other induction questions! 0 1 + (2? 0) 0 1 + (2? 2) Work out each term 1 + 2 2(2?) 1 BASIS 2(2?) 0 Simplify (remember to manipulate the powers) ASSUMPTION INDUCTIVE CONCLUSION 1 2?+1 1 2?+1 0 1 2?+1 2?+1 =1 0 8C

Proof by Induction CONCLUSION We assumed that: You can use proof by induction to prove general statements involving matrix multiplication ? 1 2? 2? 1 0 1 2 =1 ?? ???? ??? ? + 0 Use mathematical induction to prove that: Using this, we showed that: ? 1 2? 2? 1 0 1 2 =1 ??? ? + ?+1 1 2?+1 2?+1 1 0 1 2 =1 0 0 As always, follow the same pattern as with the other induction questions! As you can see, all the k terms have been replaced with k + 1 terms BASIS Therefore, IF the statement is true for one term, it will also be true for the next term, and so on ASSUMPTION INDUCTIVE CONCLUSION As we already showed that the statement is true for n = 1, it is therefore true for all values of n! 8C

Proof by Induction BASIS Show that the statement is true for n = 1 You can use proof by induction to prove general statements involving matrix multiplication ? = 3? + 1 9? 2 1 9 4 ? 3? + 1 Use mathematical induction to prove that: Replace n with 1 Replace n with 1 ? = 3? + 1 9? 2 1 9 4 ??? ? + 1 ? 3? + 1 3 1 + 1 (1) 9(1) 3 1 + 1 2 1 9 4 Calculate Calculate More complicated, but the same process! = 2 9 4 = 2 9 4 1 1 BASIS So the statement is true for n = 1 ASSUMPTION INDUCTIVE CONCLUSION 8C

Proof by Induction ASSUMPTION Assume the statement is true for n = k You can use proof by induction to prove general statements involving matrix multiplication ? 2 1 9 4 = 3? + 1 9? ?? ???? ??? ? + ? 3? + 1 Use mathematical induction to prove that: INDUCTIVE Show using the assumption, that the statement will then be true for n = k + 1 ? = 3? + 1 9? 2 1 9 4 ??? ? + ? 3? + 1 ? 2 1 1 ?+1 = 2 9 4 9 4 2 1 9 4 Replace the power k term with the assumed matrix The second matrix doesn t need the power! 1 More complicated, but the same process! = 3? + 1 9? 2 1 9 4 ? 3? + 1 BASIS ASSUMPTION INDUCTIVE CONCLUSION Now we need to multiply these matrices using the skills from chapter 4! 8C

Proof by Induction INDUCTIVE Show using the assumption, that the statement will also be true for n = k + 1 You can use proof by induction to prove general statements involving matrix multiplication ? 2 1 1 ?+1 = 2 9 4 9 4 2 1 9 4 Replace the power k term with the assumed matrix The second matrix doesn t need the power! 1 Use mathematical induction to prove that: = 3? + 1 9? 2 1 9 4 ? ? 3? + 1 = 3? + 1 9? 2 1 9 4 ??? ? + ? 3? + 1 ( 3? + 1 2) + (9? 1) ( 3? + 1 9) + (9? 4) Simplify terms (probably a good idea to do in stages ) More complicated, but the same process! ( ? 2) + ((3? + 1) 1) ( ? 9) + ((3? + 1) 4) (6? 2) + ( 9?) ( 27? + 9) + (36?) BASIS (2?) + ( 3? 1) ( 9?) + (12? + 4) ASSUMPTION INDUCTIVE CONCLUSION Simplify fully 3? 2 9? + 9 ? 1 3? + 4 This is the answer to the multiplication = 3? 2 ? 1 9? + 9 3? + 4 8C

Proof by Induction CONCLUSION We assumed that: You can use proof by induction to prove general statements involving matrix multiplication ? 2 1 9 4 = 3? + 1 9? ?? ???? ??? ? + ? 3? + 1 Use mathematical induction to prove that: Using this, we showed that: ?+1 Each part of the matrix can be written differently (you will see why in a moment!) 2 1 9 4 = 3? 2 ? 1 9? + 9 3? + 4 ? = 3? + 1 9? 2 1 9 4 ??? ? + ? 3? + 1 3 ? + 1 + 1 (? + 1) 9(? + 1) 3 ? + 1 + 1 = More complicated, but the same process! If you compare this to the original matrix, you can see that all the k terms have been replaced with k + 1 terms BASIS ASSUMPTION INDUCTIVE CONCLUSION So we have shown that if the statement is true for n = k, it will also be true for n = k + 1 As it was true for n = 1, it is also true for all positive values of k! 8C