Induction: for really tall buildings

Prologue: In which there is a picture of a ladder, a metaphor is made, and Dashbo asks you to do a lot of senseless adding.

This is induction

Induction is a ladder. This ladder has some interesting properties to it. First, you can always get to the bottom rung on the ladder. Second, if you can get to any rung on the ladder, then you can get to the next rung as well. So does it make sense that you can get to any rung on the whole ladder? (because you can get to rung 1 and that means you can get to rung 2 and since you are there, you can get to number 3 etc.)

Induction is a ladder that proves some kind of math-something-or-other. And making this ladder takes two steps. (steps is a word which here means "any maneuver made as part of progress toward a goal") but once you have established this ladder, it usually has an infinite number of steps. (steps is a word which here means "rungs on a ladder")
Have you ever had to add all the numbers from 1 to one gajillion? Well then induction is the ladder for you! But the really slick part is that you don't need to actually climb the infinite latter, just make it and walk away!
Let us start by adding something smaller from 1 to . . . 1. Yes all the numbers from one to one should be fairly easy to add. it is just 1
lets do another slightly complicated one: 1 through 2
1+2=3     Done and done!
lets keep going a little bit more
1=1
1+2=3
1+2+3=6
1+2+3+4=10
1+2+3+4+5=15
Is there an easy to see pattern? Well, there is and some guy named Gauss figured it out when he was a baby or something. He wasn't the first, but later in life, he drew a really famous 17-sided polygon so we give him the credit. Today, I could show you how to draw a picture that makes it really obvious but I am not going to. Instead, you get the inductive proof. If you want to see Gauss's way of thinking about it, maybe you should start your own math blog. I won't be offended.

Jerk.

To see the pattern, lets call the last number that we add "n." So we want to add from 1 to n and it just so happens to be

Are you going to take my word for it? Well you whatever your answer is to that question is, I am going to show you the proof so it doesn't matter what you think.
Now on to the two steps of building an inductive proof!

Chapter 1: The Base Case This is a short chapter in which we get to the first rung on the ladder and add all the numbers from 1 to 1. Yes, again.

In the base case we have to get to the bottom rung. So let us just try it with our little formula for n=1. We already know that it equals 1 because we added it in the prologue. but just for fun, we'll do it the other way:

Oh good! It works for the first rung in our ladder! And since numbers don't really ever change, this is always true for ever and ever so far as I can tell.

Chapter 2: The Inductive Step In which we climb the ladder from any rung to the next rung up and somehow climb the whole thing without actually climbing at all.

 Now is the tricky part. We need to show that going from one step to the next is always going to be the same thing. We start with an assumption:
Suppose our formula is true for any number n. I already told you it is true so you might have already assumed it is true. Remember this image?

It is a rerun from earlier in the blog post

I do. I got it from Wikipedia
well if that is true then climbing to the next rung is to try "n+1"
using our keen algebra skills, lets add n+1 to both sides of the equation. 

We are almost done! If all the junk on the right-hand side can be put into a form that looks like our formula, then it is done and we can go home! (with new knowledge!!!)
to do that, lets take our part we just added and multiply by 2 divided by 2, (2/2)

 

This lets us turn the whole mess into one fraction since they now have a 2 on the bottom.

Notice how there is an "n" and a "2" on top that are both multiplying an (n+1)? We want to get those (n+1)'s together. We do this by factoring. Remember the water-bottle example? If the 2 and the n are both being multiplied by an (n+1) then the rules say it is 100% legal to stick them in the same package and just multiply that by the (n+1). This is the result:

 So now, it is super easy to take that 2 on top and turn it into a 1+1. It will make that part of the equation look like (n+1+1) And finally, we just add some more plastic wrap to that and exclude one of the 1's (since one is the loneliest number anyway.)

Whoa! Did you see the magic happen? We said in that rerun image that 1 to a number n is that neat little formula. We didn't prove THAT part, we just assumed it to be true. But from that, we showed that we can add the next number (n+1) and what did we end up with? THE EXACT SAME FORMULA BUT FOR THE NEXT NUMBER!!!!!

Epilogue: In which we reflect on the significance of something.

In the Inductive step we really only proved that IF true for some number, THEN it is true for the next number. This really doesn't mean much unless you remember the base case.

But it IS true for n=1 and so it MUST ALSO BE TRUE FOR 2 AND 3 AND 4 AND . . . EVERY WHOLE NUMBER BIGGER THAN 1!!!!!

Let us reflect on the significance of this: We can now solve our "add all numbers from 1 to one gajillion" problem. it would be (one gajillion) x (one gajillion + 1) divided by 2. HOORAY FOR ENDLESS MATH LADDERS!!!

That wasn't too shabby was it?