Sean Leonard

IST 230 — Section 2

9/1/00

Mathematical Induction

Mathematical induction is just a fancy way of proving equations. Although it seems difficult at first, it’s only a few steps you have to remember. This problem can be found in your book on page 16, number 1.

We start with the identity: 2 + 4 + 6 + … + 2n = n*(n + 1)

The very first step (called the **basis step) **is to substitute a value into the equation to make sure it holds true. It really doesn’t matter what value you pick, but it’s easiest to use 0 or 1. I’ll use 0 for the example: 2*0 = 0*(0+1)

Clearly we can see that 0 = 0. Thus, the equation has passed the first test. The next step (called the **induction step**) is instead of substituting a value into ‘n’ we substitute ‘n + 1’ in for n. The reasoning behind this will be clearer in further sections of the book, but for now, just realize that we’re *assuming* that the equation works with ‘n’ and we are trying to prove it *will work* with ‘n + 1’

The equation now becomes: 2 + 4 + 6 … + 2n + 2*(n + 1) = (n + 1)*({n + 1} + 1)

Do you notice anything? Part of the equation above is very similar to our original equation. Both contain "2 + 4 + 6 + … + 2n." We are assuming that the original identity is *true* and can plug the value "n*(n + 1)" instead. This means our new equation looks like this: n*(n + 1) + 2*(n + 1) = (n + 1)*(n + 2) ß
(n+1+1 becomes n+2)

Now, the final step is simply to simplify the left side of the equation. Because (n + 1) is in both terms we can factor it out giving us on the left side: (n + 1)*(n + 2)

At this point we can stop because the left and right sides are both the same. This means that the equation is valid and will hold for values of x. There you go, that’s all there is to mathematical induction!