On Tue, May 6, 2008 at 5:34 AM, PR Stanley <[EMAIL PROTECTED]> 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
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
