On Tue, May 6, 2008 at 5:34 AM, PR Stanley <
prstanley@ntlworld.com> wrote:
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
For a more intuitive view, mathematical induction (at least, induction over the integers) is like knocking over a chain of dominoes. To knock over the whole (possibly infinite!) chain, you need two things:
1. You need to make sure that each domino is close enough to knock over the next.
2. You need to actually knock over the first domino.
Relating this to proving a proposition P for all nonnegative integers, step 1 is like proving that P(k) implies P(k+1) -- IF the kth domino gets knocked over (i.e. if P(k) is true), then it will also knock over the next one (P(k) implies P(k+1)). Step 2 is like proving the base case -- P(0) is true.
Hopefully this helps you get a more intuitive view of what induction is all about; you can use some of the other responses to fill in more details.
-Brent