Am Dienstag, 6. Mai 2008 11:34 schrieb PR Stanley:
Hi I don't know what it is that I'm not getting where mathematical induction is concerned. This is relevant to Haskell so I wonder if any of you gents could explain in unambiguous terms the concept please. The wikipedia article offers perhaps the least obfuscated definition I've found so far but I would still like more clarity. The idea is to move onto inductive proof in Haskell. First, however, I need to understand the general mathematical concept.
Top marks for clarity and explanation of technical terms. Thanks Paul
Mathematical induction is a method to prove that some proposition P holds for all natural numbers. The principle of mathematical induction says that if 1) P(0) holds and 2) for every natural number n, if P(n) holds, then also P(n+1) holds, then P holds for all natural numbers. If you choose another base case, say k instead of 0, so use 1') P(k) holds, then you can deduce that P holds for all natural numbers greater than or equal to k. You can convince yourself of the validity of the principle the following ways: Direct: By 1), P(0) is true. Specialising n to 0 in 2), since we already know that P(0) holds, we deduce that P(1) holds, too. Now specialising n to 1 in 2), since we already know that P(1) is true, we deduce that P(2) is also true. And so on ... after k such specialisations we have found that P(k) is true. Indirect: Suppose there is an n1 such that P(n1) is false. Let n0 be the smallest number for which P doesn't hold (there is one because there are only finitely many natural numbers less than or equal to n1. Technical term: the set of natural numbers is well-ordered, which means that every non-empty subset contains a smallest element). If n0 = 0, 1) doesn't hold, otherwise there is a natural number n (namely n0-1), for which P(n) holds but not P(n+1), so 2) doesn't hold. Example: The sum of the first n odd numbers is n^2, or 1 + 3 + ... + 2*n-1 = n^2. 1) Base case: a) n = 0: the sum of the first 0 odd numbers is 0 and 0^2 = 0. b) n = 1: the sum of the first 1 odd numbers is 1 and 1^2 = 1. 2) Let n be an arbitrary natural number. We prove that if the induction hypothesis - 1 + 3 + ... + 2*n-1 = n^2 - holds, then 1 + 3 + ... + 2*(n+1)-1 = (n+1)^2 holds, too. 1 + 3 + ... + 2*(n+1)-1 = (1 + 3 + ... + 2*n-1) + 2*(n+1)-1 = n^2 + 2*(n+1) -1 -- by the induction hypothesis = n^2 + 2*n + 1 = (n+1)^2 cqfd. Hope this helps, Daniel