<br><div class="gmail_quote">On Tue, May 6, 2008 at 5:34 AM, PR Stanley <<a href="mailto:prstanley@ntlworld.com">prstanley@ntlworld.com</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi<br>
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.<br>
The wikipedia article offers perhaps the least obfuscated definition I've found so far but I would still like more clarity.<br>
The idea is to move onto inductive proof in Haskell. First, however, I need to understand the general mathematical concept.<br>
<br>
Top marks for clarity and explanation of technical terms.<br>
Thanks<br>
Paul<br>
</blockquote><div><br>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:<br>
<br>1. You need to make sure that each domino is close enough to knock over the next.<br>2. You need to actually knock over the first domino.<br><br>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.<br>
<br>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.<br><br>-Brent<br></div></div><br>