Induction.md (2772B)
1 # Induction Proof 2 3 Proof by induction from W11 abstract algebra. Induction is used to prove a statement relating to infinite sets of elements. This is not to be confused with inductive reasoning which is assumptions based on past data. 4 5 **Definition:** This type of proof is done by proving that the first is true and how that subsequently means the rest are true (think dominoes). 6 7 Steps to prove: 8 1. Prove first statement is true 9 2. Prove that the statement $S_k \implies S_{k+1}$ is true. 10 11 **Basis Step:** The first step above is called the basis step because $S_1$ is generally quite simple. 12 13 **Inductive Step:** The second step above is called the inductive step. This is most commonly done via direct proof ie. assuming $S_1$ is true. 14 15 **Inductive Hypothesis:** This is the assumption that $S_k$ is true. Based on this assumption, we must then prove that it follows $S_K \implies S_{k+1}$. 16 17 To prove this, it seems, we need to first prove that the 0th or first (generally) term of the sequence is true. This will generally be 0 or 1 indexed so such proofs are generally straightforward. Then we find an elements written out form, and then we find it's form + 1 in the index. Using this technique we should be able to show that the +1 index is in some way related to the +0 index. 18 19 I am not sure if you need to prove the first element or if the logic to backpropogate is sufficient. 20 21 Use if then notation for the current so that if the first then the second. Since we know the first we then need to prove the then follows logically in all cases across the domain of the function. 22 23 If the set of numbers is bidirectional like $\Z$, then we need to prove that both $S_n \implies S_{n+1}$ and that $S_n \implies S_{n-1}$ for all numbers in the domain. 24 25 When using induction the common form is $S_k \implies S_{k+1}$, but it is equally valid to prove that $S_{k-1} \implies S_k$ if that is easier to show. 26 27 When proving induction it is important to first state what the value of k+1 equates to. We then need to go from there to equate it to the other side of the statement. We should not assign the left and right together from the start because there would be nowhere to go from there instead do algebra to prove the statement is true. 28 29 [StrongInduction](StrongInduction.md) Is another type of induction. 30 31 See also [SmallestCounterExample](SmallestCounterExample.md) for something similar to [[CounterExample.md]] of [[Induction.md]] 32 33 It is important to note that a set must be [WellOrdered](WellOrdered.md) for it to be possible to prove by induction. 34 35 Another interesting thing that relates to induction is [FibonacciNumbers](FibonacciNumbers.md) in the sense that they are entirely reliant upon previous calculations to determine the next value in the set.