Talk:Mathematical induction
Add topicMathematical Induction is the "dominoes theory" of proof. It is often used when you want to prove something is true for every whole number, but don't have time to prove all the infinite cases one by one. It has two parts: line up the dominoes, and knock over the first one. Lining up the dominoes means you prove that if the statement is true for one number, it's true for the next number. Knocking over the first domino is just proving that it works for the first number (usually one.) Mathematicians call these the Induction Step and the Base Case.
For example: Suppose you want to prove that 1+2+3+...+n = n(n+1)/2. What you do is first show that if it works for k, then it works for k+1. Note: To prove an if-then statement, you assume the "if" part is true, and show the "then" part has to be true. So here, we assume 1+2+3+...+k = k(k+1)/2 for any one k. (No, this isn't circular reasoning, it just looks like it!) What we have to show is that 1+2+3+...+k+(k+1) = (k+1)(k+1+1)/2. How? We use our assumption, and substitute it on the left. So we get k(k+1)/2 + (k+1)= (k*k +k)/2 + (2k+2)/2= (k*k +3k +2)/2= (k+1)(k+2)/2 (by factoring) =(k+1)(k+1+1)/2 so it works. What did we just show? We showed that IF the formula works for k, THEN it works for k+1. And we didn't say what k was in advance. This means that we've proven that: if it works for 1, it works for 2, and if it works for 2, it works for 3, and if it works for 3, it works for 4, and so on. We're done lining up the dominoes. But we're not done! We haven't knocked any dominoes over yet! There's one more step: the Base Case. We have to knock over the first domino. When n=1, 1+2+3+...+1 just means "1", and n(n+1)/2 means 1(1+1)/2=1. So since 1=1, the first domino has fallen. And since if it works for 1, it works for 2, we know that the formula works for 2 now. And since if it works for 2, it works for 3, we know the formula works for 3 now, with no extra work. And since if it works for 3, it works for 4, and so on, we know the formula ALWAYS WORKS. We've proven it for every natural number! That's mathematical induction.
There's also a fancier version called Strong Induction, which is a lot like setting up those pretty branching lines of dominoes. Essentially, you get to assume that the formula works for every number up to k, and then have to show it works for k+1. This is good for problems where you can cut the problem up into something smaller, but not necessarily one unit smaller.
Start a discussion about Mathematical induction
Talk pages are where people discuss how to make content on Wikiversity the best that it can be. You can use this page to start a discussion with others about how to improve Mathematical induction.
