Binomial Theorem with Induction

The principle of mathematical induction is one of the most fundamental proof techniques out there, and it is one of the first proof techniques typically introduced in a proof-writing class. It lends itself well to proving statements that we wish to be true for all natural numbers, and thus, it sees use in combinatorics, which involves counting objects. If you are counting objects you have to have a natural number of them, right?

Anyway, the idea behind mathematical induction is as follows: say your statement to be proven is S(n). Then what you do first is prove the statement for n = 0, which is usually quite easy. We say that S(0) has been proven.

Now, we let n be any natural number, and here’s where the heads start to turn a little bit. We assume that S(n) is true.

Wait, what? Isn’t that what we wanted to prove?

Sort of, but listen to what comes next. Using this assumption we prove that S(n + 1) must also be true. But now n could be any natural number and we don’t get to choose it. This is good, because we already proved S(n) when n = 0. So, if we prove S(n + 1) is true whenever S(n) is true, we can replace n with 0 and conclude that S(1) is true. But if we replace n with 1, then we also get that S(2) is true; then replacing n with 2 we also get that S(3) is true. You probably get the idea by now. That’s how mathematical induction works: you prove S(n) for n = 0, and then you prove that whenever S(n) is true for the previous value of n, it is also true for the next value, which…