[Haskell-cafe] Induction (help!)
Daniel Fischer
daniel.is.fischer at web.de
Tue May 6 09:15:28 EDT 2008
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
More information about the Haskell-Cafe
mailing list