## Proof by Mathematical Induction [62e9398a9d62] Mathematical induction is a method of proof used to establish that a statement is true for all natural numbers. The main idea is that you assume that the statement is true for some natural number. Then you show, that if it is true for that natural number, then it is true for the next. Hence, if you find it is true for some number, then this means it is true for the next, hence it is true for the next, and so on, proving for it is true for all numbers greater. ### Steps [8610c05479f2] It consists of a few main steps (and one extra but important step for the examinations): 1. Call your statement $P(n)$. For example, "$P(n)$: $n(n+1)(n+2)$ is divisible by $6$ for all numbers $n\in\mathbb{N}$." 2. Base case: Prove the statement is true for the smallest value (usually $n = 1$ or $n = 0$, but there can be others, so make sure to check what the smallest possible value is). Call this $P(1)$ or $P(0)$ (or whatever number you're using as the base case). 3. Inductive hypothesis: Assume $P(k)$ holds for some number $k\in\mathbb{N}$ - i.e. the statement is true for some arbitrary natural number $k$. Let this $k$ be bigger than or equal to the number you used in your base step. 4. Inductive step: Hence, now prove $P(k+1)$ holds if $P(k)$ holds – i.e. the statement is true for $k+1$ **if** it is true for $k$. **Make sure** to use your inductive hypothesis somewhere – this is what differentiates proof by induction from proof by deduction. 5. (Extra but important) Conclusion: Make sure to give a conclusion that $P(k+1)$ holds if $P(k)$ holds for $k\in\mathbb{N}$, and $P(\text{base case})$ holds, therefore $P(n)$ holds for all $n \geq \text{base case}$. [{"_key":"ab87b25abffd","_type":"block","asset":null,"children":[{"_key":"cd84a507ad80","_type":"span","marks":[],"text":"Let's prove that the sum of the first $n$ positive integers is given by the formula:"}],"markDefs":[],"style":"normal"},{"_key":"d348f962b1a1","_type":"block","asset":null,"children":[{"_key":"75c68e61a4da","_type":"span","marks":[],"text":"$$P(n): S_n = \\frac{n(n+1)}{2} $$"}],"markDefs":[],"style":"normal"},{"_key":"c022d3d3103d","_type":"block","asset":null,"children":[{"_key":"0d801442ee30","_type":"span","marks":["strong"],"text":"Base case ($n = 1$):"},{"_key":"3d78b0280282","_type":"span","marks":[],"text":" $P(1): S_1 = 1 = \\frac{1(1+1)}{2} = 1$, so $P(n)$ holds for $n = 1$."}],"markDefs":[],"style":"normal"},{"_key":"4fa1c556e657","_type":"block","asset":null,"children":[{"_key":"fd3f0df02815","_type":"span","marks":["strong"],"text":"Inductive hypothesis:"},{"_key":"e77bb0f5b3a3","_type":"span","marks":[],"text":" Assume $P(k)$ holds for some number $k\\in\\mathbb{N}$ where $k\\geq1$, i.e., $S_k = \\frac{k(k+1)}{2}$"}],"markDefs":[],"style":"normal"},{"_key":"6e5e5c5d9f63","_type":"block","asset":null,"children":[{"_key":"8945a9969705","_type":"span","marks":["strong"],"text":"Inductive step:"}],"markDefs":[],"style":"normal"},{"_key":"c706404c06a2","_type":"block","asset":null,"children":[{"_key":"b244b27fad65","_type":"span","marks":[],"text":"$S_{k+1} = S_k + (k+1)$"}],"markDefs":[],"style":"normal"},{"_key":"d6f8736761a0","_type":"block","asset":null,"children":[{"_key":"85cb820e78f7","_type":"span","marks":[],"text":"$= \\frac{k(k+1)}{2} + (k+1)$"}],"markDefs":[],"style":"normal"},{"_key":"6bfcf84999c8","_type":"block","asset":null,"children":[{"_key":"e60ec1920727","_type":"span","marks":[],"text":"$= \\frac{k(k+1) + 2(k+1)}{2}$"}],"markDefs":[],"style":"normal"},{"_key":"e20a60b0e0aa","_type":"block","asset":null,"children":[{"_key":"d58de30622cc","_type":"span","marks":[],"text":"$= \\frac{(k+1)(k+2)}{2}$"}],"markDefs":[],"style":"normal"},{"_key":"2d0ea86d0bf2","_type":"block","asset":null,"children":[{"_key":"5e8d1cfa62a4","_type":"span","marks":[],"text":"This is exactly the formula for $n = k + 1$, thus $P(k+1)$ holds if $P(k)$ holds."}],"markDefs":[],"style":"normal"},{"_key":"c2bd2d2415c8","_type":"block","asset":null,"children":[{"_key":"1d0be65c13bc","_type":"span","marks":["strong"],"text":"Conclusion: "},{"_key":"2c9fec355c25","_type":"span","marks":[],"text":"$P(k+1)$ holds if $P(k)$ holds, and $P(1)$ holds. Thus, $P(n)$ holds for all $n\\in\\mathbb{N}$."}],"markDefs":[],"style":"normal"}] [{"_key":"SKegYEUhosFtAcmMhchDZV","_type":"block","asset":null,"children":[{"_key":"SKegYEUhosFtAcmMhchDcf","_type":"span","marks":[],"text":"In exams, follow "},{"_key":"a38304d068a8","_type":"span","marks":["strong"],"text":"this exact structure"},{"_key":"b79a6b14d16f","_type":"span","marks":[],"text":", including the notation $P(n)$. Don't add or remove anything – this could put you at risk of being docked marks."}],"markDefs":[],"style":"normal"}] [{"_key":"8ec972d71821","_type":"block","asset":null,"children":[{"_key":"a667302f6950","_type":"span","marks":[],"text":"Prove that $n^3 - n$ is divisible by $6$ for all $n\\in\\mathbb{N}$:"}],"markDefs":[],"style":"normal"},{"_key":"4437fa7441ac","_type":"block","asset":null,"children":[{"_key":"cd7dcf2f1b32","_type":"span","marks":[],"text":"deductively"}],"level":2,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"7c12be412400","_type":"block","asset":null,"children":[{"_key":"edf7e4e9a89e","_type":"span","marks":[],"text":"inductively."}],"level":2,"listItem":"number","markDefs":[],"style":"normal"}] ## Proof by Contradiction [ae5be8bee2af] Proof by contradiction is a method where we assume the opposite of what we want to prove, and then show that this assumption leads to a logical contradiction. This implies that our original statement must be true. [{"_key":"abe2bf964f2b","_type":"block","asset":null,"children":[{"_key":"63e4aeef2162","_type":"span","marks":[],"text":"Let's prove that $\\sqrt3$ is irrational."}],"markDefs":[],"style":"normal"},{"_key":"510ac71f758b","_type":"block","asset":null,"children":[{"_key":"1cc2c8ef83b9","_type":"span","marks":[],"text":"Assume $\\sqrt3$ is rational. This means it can be expressed as a fraction $\\frac{a}{b}$ where a and b are integers with no common factors."}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"221644e5d10e","_type":"block","asset":null,"children":[{"_key":"361ab6ee61f0","_type":"span","marks":[],"text":"If this is true, then $\\frac{a}{b} = \\sqrt{3}$"}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"1c4de25c717a","_type":"block","asset":null,"children":[{"_key":"18cb349e9625","_type":"span","marks":[],"text":"Square both sides: $\\frac{a^2}{b^2} = 3$"}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"bca3ea3a5ef8","_type":"block","asset":null,"children":[{"_key":"2fbf6539ba0f","_type":"span","marks":[],"text":"Multiply both sides by $b^2$: $a^2 = 3b^2$"}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"3157558fe555","_type":"block","asset":null,"children":[{"_key":"c037d4b2f0d0","_type":"span","marks":[],"text":"This means $a^2$ is divisible by 3, which implies a is divisible by 3. Let $a = 3k$ for some integer k."}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"1510d0c68cfc","_type":"block","asset":null,"children":[{"_key":"bcad54a39435","_type":"span","marks":[],"text":"Substitute this back: $(3k)^2 = 3b^2$"}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"7e99726f7cf7","_type":"block","asset":null,"children":[{"_key":"431a5d98d3e9","_type":"span","marks":[],"text":"Simplify: $9k^2 = 3b^2$"}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"6192dabec1f1","_type":"block","asset":null,"children":[{"_key":"06c82b586425","_type":"span","marks":[],"text":"Divide by 3: $3k^2 = b^2$"}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"a3b508e2b5d4","_type":"block","asset":null,"children":[{"_key":"ee799451f8e3","_type":"span","marks":[],"text":"This means $b^2$ is divisible by 3, which implies b is divisible by 3."}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"ba68e19d2e05","_type":"block","asset":null,"children":[{"_key":"e1715598e8a5","_type":"span","marks":[],"text":"But this contradicts our initial assumption that a and b have no common factors."}],"level":1,"listItem":"number","markDefs":[],"style":"normal"},{"_key":"b8a7066ca762","_type":"block","asset":null,"children":[{"_key":"b067cfc4ef58","_type":"span","marks":[],"text":"Therefore, our initial assumption must be false, and √3 must be irrational."}],"markDefs":[],"style":"normal"}] [{"_key":"SKegYEUhosFtAcmMhchDfp","_type":"block","asset":null,"children":[{"_key":"SKegYEUhosFtAcmMhchDiz","_type":"span","marks":[],"text":"Students often forget to clearly state the contradiction and explain why it invalidates the initial assumption."}],"markDefs":[],"style":"normal"}] ## Counterexamples [c118bbe89aaf] A counterexample is a specific case that disproves a general statement. It's a powerful tool to show that a statement is not always true. [{"_key":"21f8a0e574c9","_type":"block","asset":null,"children":[{"_key":"0af0cf6664c5","_type":"span","marks":[],"text":"All elements of P are prime"}],"markDefs":[],"style":"h3"},{"_key":"5580a4440b09","_type":"block","asset":null,"children":[{"_key":"65bb93e393db","_type":"span","marks":[],"text":"Consider the set $P$ of numbers of the form $n^2 + 41n + 41$, where $n$ is a natural number."}],"markDefs":[],"style":"normal"},{"_key":"a74fe60e6a12","_type":"block","asset":null,"children":[{"_key":"01d0f74ad841","_type":"span","marks":[],"text":"To disprove that all elements of $P$ are prime, we need to find a value of $n$ for which $n^2 + 41n + 41$ is not prime."}],"markDefs":[],"style":"normal"},{"_key":"1dab868e512e","_type":"block","asset":null,"children":[{"_key":"4ee73ff81c49","_type":"span","marks":[],"text":"Let's try $n = 41$:"}],"markDefs":[],"style":"normal"},{"_key":"9fe5cf115fa7","_type":"block","asset":null,"children":[{"_key":"bd33161eda1d","_type":"span","marks":[],"text":"$41^2 + 41(41) + 41 = 1681 + 1681 + 41 = 3403 = 41 \\times 83$"}],"markDefs":[],"style":"normal"},{"_key":"cdd0dfc77186","_type":"block","asset":null,"children":[{"_key":"2f88cc7e00d9","_type":"span","marks":[],"text":"This is not a prime number as it's divisible by 41 and 83."}],"markDefs":[],"style":"normal"}] [{"_key":"SKegYEUhosFtAcmMhchDm9","_type":"block","asset":null,"children":[{"_key":"SKegYEUhosFtAcmMhchDpJ","_type":"span","marks":[],"text":"When using a counterexample, it's crucial to explain why the example contradicts the given statement, not just state the example."}],"markDefs":[],"style":"normal"}] [{"_key":"1ea5193625e7","_type":"block","asset":null,"children":[{"_key":"8cb0e3f5ab67","_type":"span","marks":[],"text":"Proof by induction is mostly seen on papers 1 and 2, while proof by contradiction and counterexample are most often seen on paper 3."}],"markDefs":[],"style":"normal"}]