Originally Posted by
Matt Westwood It works like this.
You've got a proposition involving n that you're trying to trying to prove is true for all n. (The usual example is $\displaystyle 1+2+3+...+n = \frac {n(n+1)}2$).
First you show it's true for n=1 (or n=0, or whatever, depends on the expression). In the above case, we have $\displaystyle 1 = \frac {1(1+1)}2$. This is called the "basis for the induction (or the "base case").
Then you say: "Suppose this proposition is true for $\displaystyle n=k$, where $\displaystyle k$ is any number $\displaystyle \ge 1$. Let's just, for a time being, assume that it's true." In the above example, we see that means $\displaystyle 1+2+3+...+k = \frac {k(k+1)}2$. This is called the "induction hypothesis".
Now, if by assuming that it's true for $\displaystyle k$, we can prove it's true for $\displaystyle k+1$, we know that it will then be true for all $\displaystyle n$. This is called the "induction step".
In the above, we want to show that $\displaystyle 1+2+3+...+k+(k+1)= \frac {(k+1)((k+1)+1)}2 = \frac {(k+1)(k+2)}2$.
And we do that by saying:
$\displaystyle 1+2+3+...+k+(k+1)$
$\displaystyle = \frac {k(k+1)}2+(k+1)$ (we've used the induction hypothesis here, which we temporarily assumed true above)
$\displaystyle = \frac {(k+1)(k+2)}2$ (by some fairly straightforward algebra)
And so we have shown that:
IF $\displaystyle 1+2+3+...+k = \frac {k(k+1)}2$ is true,
THEN $\displaystyle 1+2+3+...+k+(k+1)= \frac {(k+1)(k+2)}2$ is true.
And we already know that it's true when k=1.
So, "by the principle of mathematical induction", or "by mathematical induction", or just "by induction", $\displaystyle 1+2+3+...+n = \frac {n(n+1)}2$ is true for ALL values of n.
See how it works? Now see how I've applied the above to the question you asked.
It's true for 1. And, if it's true for $\displaystyle k$, then it's true for $\displaystyle k+1$.
Because it's true for 1, it's true for 1+1=2. And because it's true for 2, it's true for 2+1 = 3. And because it's true for 3, it's true for 3+1 = 4. And so on. Thus it's true for all numbers, by the fact that the numbers all go 1, 2, 3, 4, ... and so on "to infinity".
There are several underlying philosophical questions underlying the validity of the above. So much so, that the "principle of induction" is taken as an axiom (that is, a "postulate", or "basic truth") of the system of natural numbers. So don't take it too much to heart if you're not sure it "makes sense" or feel that the reasoning seems a little flimsy - the logical justification is a deep question.