[Haskell-cafe] Induction (help!)

[Daniel Fischer]

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