Mathematical induction is a standard proof technique used to show that some statement or property holds for all positive integer values of... something. Yeah, that's really vague. How about an example? We'll use a fake one, of course.
Let's say you have an old toothbrush with N bristles. You're pretty sure that every old toothbrush is bumpy. Induction might be a great way to prove it, because you could use it to show that no matter what positive-integer number of bristles the toothbrush has, the property of being bumpy holds.
Okay. So, how does this lovely proof technique work? There are three steps:
(Base Case) Check to make sure that whatever you want to prove holds for small positive integers, like 1, 2, or 3.
(Inductive Hypothesis) Assume that whatever you want to prove is true, as long as the positive integer in question is smaller than or equal to K.
(Inductive Step) Use your knowledge that things are true for K in order to show that they're still true for K+1.
It's time for another fake example. Let's say that we want to show that every Vogelplex with a finite number of horns has two fewer legs than horns.
(Base Case) We need to make sure that a Vogelplex with three horns has only one leg. Notice that we use 3 as our base case because using one horn wouldn't work (no Vogelplex has a negative number of legs) and using two horns would be unnerving (poor Vogelplex, having no legs!).
(Inductive Hypothesis) We assume that a Vogelplex with K horns has K-2 legs. Also, a Vogelplex with K-1 horns has K-3 legs, and so on down to the base case.
(Inductive Step) We show that every Vogelplex with K+1 horns has K-1 legs, using the assumption that a Vogelplex with K or fewer horns has K-2 legs. It's tempting to just add one to the inductive hypothesis in order to show the inductive step, but that doesn't work. How do we add a horn to a Vogelplex? This brings up a crucial point -- in order to do a proof by induction, we need to understand how Vogelplex with K+1 horns are related to other Vogelplex with K horns. If there's no relationship, we can't use induction. And if it happens that the number of legs on a Vogelplex is related to the shape of their spots, rather than the number of horns, we're also sunk.
We'll return to the Vogelplex later, but now, how about a real example? We have the sets {1}, {1,2}, {1,2,3}, ... {1,2,3,...,K}, ... and so on. We want to show that the set of the first N counting numbers has 2^N subsets.
(Base Case) The subsets of {1} are {} and {1}. There are two of them, which
is 2^1. Excellent.
(We're done, but if you feel insecure, note that the subsets of {1,2} are {},
{1}, {2}, {1,2}, and there are four of them, or 2^2.)
(Inductive Hypothesis) We assume that a set with the first K counting numbers has 2^K subsets.
(Inductive Step) Examine the set {1,2,..., K+1}. Every subset has one of two properties, (a) K+1 is not an element or (b) K+1 is an element. All the subsets with property (a) are actually subsets of {1,2,..., K}and so we know there are 2^K of them by the Inductive Hypothesis. And, if we take each of the property (a) subsets, and stick the element K+1 in, we get all the subsets with property (b). So there are the same number of them, and there are 2^K subsets with property (b). In total, we have 2^K + 2^K = 2 2^K = 2^(K+1) subsets, and we're done.
Often, I think of using induction as like climbing a ladder. The Base Case is like getting onto the ladder, near the bottom. The Inductive Hypothesis is like assuming I can get to the Kth rung. And, the Inductive Step tells me I know how to climb from the Kth rung to the K+1st rung. After all, what do you need to know in order to climb a ladder? You need to know how to get on, and how to get from one rung to the next. That'll take you as high as you need to go. The fact that you know how to get from rung K to rung K+1 means you can insert any values you like for K and you can get to (let's say) rung 10 by going rung 1 to rung 2, rung 2 to rung 3, rung 3 to rung 4, rung 4 to rung 5, rung 5 to rung 6, rung 6 to rung 7, rung 7 to rung 8, rung 8 to rung 9, and rung 9 to rung 10.
There's only one problem with this analogy. (Okay, there might be more than one problem. But there's one big problem.) It only works for simple things, like the counting-numbers-set problem above. What happens if there's more than one way to get from rung K to rung K+1? Or worse, suppose there are lots of different objects which all are described by the positive integer K? An example here would be all the networks which have 5 hubs and some number of channels connecting them (or for that matter, all networks with some number of hubs connected by five channels). There are lots of ways to take a network with five hubs and create one with six hubs...way too many ways...
The correction to the ladder analogy is to think of the ladder as branching at every rung. And it doesn't just branch into two ladder-paths, but a lot of ladder-paths. And it happens at every rung, so that there are bunches of rungs at each level of the ladder. It's hard to imagine what that would look like, let alone how one would decide how to climb such a ladder. Luckily, there's a way out of this problem.
When we do proofs by induction, we don't build up from the K case to the K+1 case. What we actually do is start with the K+1 case, and find a K case from which it came. So instead of climbing up from a K-level rung to a K+1-level rung, we take some K+1-level rung and look just below it to see the K-level rung. That's much easier. And then, in order to climb to a particular spot on our multi-branching ladder, we mark it, look downward to see what rungs are under it, and then we know how to climb there. So the induction proof, in ladder terms, looks like this:
(Base Case) Make sure that we can get onto the ladder.
(Induction Hypothesis) Assume that if we happen to be on a K-level rung, we know how we got there.
(Induction Step) From a K+1-level rung, figure out how to get back to a K-level rung, so we'll know where we are.
Let's go back to our Vogelplex example. We want to show that every Vogelplex with a finite number of horns has two fewer legs than horns. We know that a Vogelplex with three horns has one leg. We assume that a Vogelplex with K horns has K-2 legs. We need to show that a Vogelplex with K+1 horns has K-1 legs, using our knowledge about Vogelplex with K horns. We could try adding a horn...but who knows how many ways there are for horns to be arranged on a Vogelplex head? Instead, let's take some Vogelplex with K+1 horns. We remove one, so we have a Vogelplex with K horns. And we notice that the screws holding on that horn were also holding on a leg. So the leg falls off, and we have a Vogelplex missing a leg. However, it has K horns, so we know it has K-2 legs. But we have an extra horn and an extra leg, which tells us that the original Vogelplex had K-1 legs, and we're done.