Proof by Mathematical Induction

Proof by mathematical inductionhttps://en.wikipedia.org/wiki/Mathematical_induction Mathematical induction is the process of verifying or proving a mathematical statement is true for all values of within given parameters. For example: We are asked to prove that is divisible by 4. We can test if it's true by giving values. So, the first 5 values of n are divisible by 4, but what about all cases? That's where mathematical induction comes in. Mathematical induction is a rigorous process, as such all proofs must have the same general format: Proposition – What are you trying to prove? Base case – Is it true for the first case? This means is it true for the first possible value of . Assumption – We assume what we are trying to prove is true for a general number. such as , also known as the induction hypothesis. Induction – Show that if our assumption is true for the ( term, then it must also be true for the ( term. Conclusion – Formalise your proof. There will be four types of mathematical induction that you will come across in FP1: Summation of series; Divisibility; Recurrence relations; Matrices. Example of a proof by summation of series (Empty) Example of a proof by divisibility Proposition: Notice our parameter, . This means that what we want to prove must be true for all values of which belong to the set (denoted by ) of positive integers (). Base case: Assumption (Induction Hypothesis): Now we let where is a general positive integer, and we assume that . Remember that . Induction: Now we want to prove that the term is also divisible by 4 Hence: This is where our assumption comes in, if then 4 must also divide . So: Now we've shown and thus . This implies that because you have successfully shown that 4 divides , where is a general, positive integer () and also the consecutive term after the general term () Conclusion: Example of a proof by recurrence relations (Empty) Example of a proof by matrices (Empty) References Mathematics