Mathematical induction

Description of Mathematical Induction (Proof by Induction)

Mathematical induction is a process of mathematical proof whereby an assumption is made about regarding the given identity being true for a particular number, then demonstrating that the proof is true for a number one greater. If it can then be shown that the proof is true for any particular number, mathematical induction then shows that it is also true for any other integer of greater value.

Picture the process of Mathematical Induction as a sequence of dominoes. 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.

Example

Suppose you want to prove the statement $1+2+3+\cdots +n={\frac {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+\cdots +k={\frac {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+\cdots +k+(k+1)={\frac {(k+1)(k+1+1)}{2}}$. How? We use our assumption, and substitute it on the left. So we get ${\frac {k(k+1)}{2}}+(k+1)={\frac {(k*k+k)}{2}}+{\frac {(2k+2)}{2}}={\frac {(k*k+3k+2}{2}}={\frac {(k+1)(k+2)}{2}}$. Then one simplifies further by factoring ${\frac {(k+1)(k+2)}{2}}$ into ${\frac {(k+1)(k+1+1)}{2}}$, thus 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.

Note

This process does not attempt to form identities which are true statements, it simply proves that a given statement is true.