\documentclass[fullpage,11pt]{article}
\begin{document}

Induction is a powerful method of proof, often useful in cases where we
 wish to prove that some statement holds for all values of an integer
 parameter, $n$, starting at some smallest value $n_0$.  For example,
 suppose we wish to prove that $\sum_{i=1}^n i = n(n+1)/2$, for all $n
 \geq 1$. Then $n_0$ will be $1$.  

 The idea behind induction is to show two things: (i) if the statement
 ever ``gets going'' by being true for some $n$ then it ``keeps
 going'' by staying true for all larger $n$ (what we might acronymize
 as SIS (StartsImpliesStays), or ForeverAfter -- if it
 ever Starts to be true then it Stays true forever after); and (ii)
 that the statement does in fact hold for the smallest value, $n_0$ (the
 so-called base case).

 We usually do the ``start'' (or base) case first, and then show the
 ``never stops'' part (the so-called inductive step); but this is
 merely a convention, and as long as we have done both parts then we
 have shown that the statement holds for all $n \geq n_0$.

 Another fanciful way to think of it is in terms of an inheritance law, eg, a
 fictitious law passed in 1800 saying that the children of every rich
 person must
 inherit all their parents' wealth.  This is not enough to guarantee
 that anyone at all is rich today, because perhaps no one happened to
 be rich in the first place.  But if we also know that person A
 was rich (say in 1890) then it follows all the
 descendants of A are rich as well, including future descendants not
 yet born.  The key fact about A (rich) then corresponds
 to the base case, and the inheritance law is the inductive step. Thus
 richness -- once it starts -- never stops (at least in this imaginary world).

 But it is a bit astonishing that one can ever show that a *mathematical*
 version of inheritance  never stops -- since we cannot expect
 Congress to pass laws guaranteeing our mathematics to come out
 right; and even if they did, we would not trust that kind of law to
 be a reliable guide to what is true.

 So how can we be sure that a math statement stays true forever after,
 ie, for all $n$  just from its
 being true for some particular $n_0$? Wouldn't we have to check it for
 every larger value of $n$, to be sure?  Yes and no.  We do check it,
 but (when the method works) we check it by showing that there is a
 very nice connection between consecutive cases of $n$. That is, we
 show that there is a mathematical inheritance law for the statement,
 a law (or inductive step) showing (when it works) that the truth of the
 statement for a given value of $n$, say $n=k$ implies its truth for
 $n=k+1$. This still seems astonishing; and there are two points to be
 aware of here: (i) induction does not always work, and (ii) when it
 works it is because the statement we are trying to prove is one
 where there is a special ``inheritance'' relation between consecutive
 cases of $n$.

 It is time to stop abstract descriptions, and see some examples.

 How would we show, for instance, that $\sum_{i=1}^n i = n(n+1)/2$ for
 all $n \geq 1$?

The forever after part requires us to show that, if the statement
(which in this case is an equation) is ever true (for some $n$, say
$n=k$) then it stays true for the next $n$, ie it ``inherits'' to
$k+1$).  We show this by 
SUPPOSING it does happen to be true for some $k$ (this is called the
inductive hypothesis, or IH):

\begin{centering}
IH: ~~~~~~ $\sum_{i=1}^k i = k(k+1)/2$
\end{centering}

NOTE: It is crucial that $k$ here be arbitrary rather than a
particular number; it is used to stand for any number at all that
might make the statement true.  This is because we are using $k$ to
show that an inheritance law holds: whenever the statement happens to
hold, for any number, then it passes its truth on to the next
number.  We use $k$ and $k+1$ simply as easy ways to refer to ``any
number'' and to ``the next number''.

We now use this supposition, IH, at $n=k$) SHOWING that the statement
stays true for the next $n$, namely $n=k+1$:

$$\sum_{i=1}^{k+1} i = (k+1)(k+2)/2$$

This always proceeds by
rewriting this new case ($k+1$) in a way that allows us to apply the
previous case ($k$), which we begin here:

$$\sum_{i=1}^{k+1} i = (k+1) + \sum_{i=1}^k$$

$$ = (k+1) + k(k+1)/2$$

We are not done; but we have taken the crucial step and the rest is
just algebra, to show that the above expression is equal to
$(k+1)(k+2)/2$.  The crucial step was to rewrite at least some piece
of the $(k+1)$ case so that the $k$ case can be applied.

Note that we ASSUME the $k$ case (the IH) -- this is the ``if it ever starts''
part -- we do NOT show it.  What we do show is that, IF it starts ($k$)
then it CONTINUES ($k+1$).  Of course, we do eventually need to show
it really does start somewhere, and that is the base case ($n_0$).
We'll get to that in a moment.  Let's first finish that inductive
step from where we left off above:


$$ = [ 2(k+1) + k(k+1) ] / 2 $$

$$ = [ 2k + 2 + k^2 + k ] / 2 $$

$$ = [ k^2 + 3k + 2 ] / 2 $$

$$ = (k+1) (k+2) / 2 $$

So we have shown that $$\sum_{i=1}^{k+1} i = (k+1)(k+2)/2$$

assuming

$$\sum_{i=1}^k i = k(k+1)/2$$

This means that the original statement, $\sum_{i=1}^n i = n(n+1)/2$,
will stay true if it ever can get ``going'', because once it has
become true for some value of $n$ then it will be true for the next
value, and since it is then true for that next value, it stay true for
the one after that, and so on.

It is essential here that $k$ NOT be taken to be any particular
constant value, such as $n_0$.  This is why what we have shown is
really  ``once-true, always-true''.  The point is that if AT ANY TIME
(ie for ANY value of $n$) the statement should happen to be true, that
it will forever remain so after that.  We need it to be this general
-- with truth flowing from ANY $n=k$ where truth might be, to the next
$n=k+1$ -- and not just that it flows from $n=n_0$ to $n=n_0 + 1$
since the latter condition would not keep the statement's truth going
on past $n=n_0 + 1$!

Does it ever ``get going'' at all?  This we quickly settle in our
present example (although sometimes it can be the hardest part).  The
base case here is $n=n_0=1$, namely:

$$\sum_{i=1}^1 i = 1(1+1)/2$$

and this is simply $1 = 1$.


Note that not all (true) statements about integers are best proven via
inductions.  For instance, it is true that if $n$ is even then $n^2$ is
even.  Here we do NOT get any advantage from induction; and a more direct
approach works just fine:  

Let $n$ be any integer. We will show that if $n$ is even then $n^2$ is
even.  Suppose $n$ is even; this means $n=2 \times k$ for some integer
$k$.  So $n^2 = 4k^2 = 2 \times (2k^2)$, so $n^2$ is twice some
integer (which is what it means to be even).  [Note: the converse is
also true: if $n^2$ is even then so is $n$, but it is harder to prove.]

============================================

There are various versions of induction.  The one presented above is
sometimes called ``ordinary'' (or weak) induction.  A fancier version
called ``course-of-values'' (or strong) induction is this: we show
that if a statement manages to ``stay true'' all the way from
$n=n_0$ to 
$n=k$ then it will also ``stay true'' at $n=k+1$. That is, we show
truth flows from an historical trend (from $n_0$ to $k$) further on to
the one more step ($k+1$).  (We also still need to show the process can
get started, so we still need a base case here, as before.)

The course-of-values version is sometimes easier to use, since to
prove the case $n=k+1$ one has a ``bigger IH'' -- more hypotheses -- to
help out (the past course of truths all the way back to $n_0$ and not
just the immediately previous step $n=k$).  

For instance one would now be able to assume not only $$\sum_{i=1}^k i
= k(k+1)/2$$ but also all the earlier cases, in trying to show
$$\sum_{i=1}^{k+1} i = (k+1)(k+2)/2$$ 

It turns out that these extra
hypotheses don't help us much in this example, so here is another
example where course-of-values induction really helps:

THEOREM: Every integer $n$ greater than 1 has a factorization into primes.

PROOF:  The base case is $n=2$, and indeed 2 has a (trivial) prime
factorization, namely itself, since 2 is prime.

Now suppose the statement of the theorem holds whenever $2 \leq n
\leq k$. This is our (strong) IH: that all integers greater than 1, up
to $k$, do have a prime factorization.  Using this, we want to show the
statement holds for $n=k+1$. Now if $k+1$ is prime, we are done. And
if it is not prime, then (by definition) it is a product $k+1 = r
\times s$ where $2 \leq r,s \leq k$. So by the IH, each of
$r$ and $s$ does have a prime factorization. But since $k+1$ is their
product, then it has the prime factorization which is the product of
the prime factorizations of $r$ and $s$.


\begin{verbatim}
                       CONSTRUCTIVE INDUCTION

Constructive induction is best learned by example.  Here is a typical
one: 

Suppose we wish to prove that 

                     SUM_i=1_to_n  i   

is a quadratic expression in n, but we don't know exactly which
expression.  (We do happen to know, in fact, that it is really
n(n+1)/2, but let's pretend we don't).

So, we try to prove the SUM above is equal to an^2 + bn + c,
where a,b,c are unknown parameters. (In trying, we will find
out what values they need to have.)  Suppose we try to prove

                    SUM = an^2 + bn + c

by induction on n, for n > 0. The base case is n=1:

                    SUM = a + b + c

which becomes
                      1 = a + b + c

since for n=1, SUM = 1.  So, we will have to make sure that
in fact a + b + c = 1, so that the base case will go through.

Now we proceed to the inductive step: Assume

IH:                 SUM = an^2 + bn + c

for some n > 0, and consider SUM_i=1_to_n+1 i.  This is

                    n+1 + SUM_i=1_to_n i

which by IH is

                    n+1 + an^2 + bn + c

and we want this to be equal to

                    a(n+1)^2 + b(n+1) + c

Setting these equal and doing some algebra:

              n+1 + an^2 + bn + c = a(n+1)^2 + b(n+1) + c

              n+1  =  2an + a + b 

Notice that c has dropped out, so we can try letting c = 0,
to make things simpler; then a + b = 1, since we had above
that a + b + c = 1.  Then

(*)           n+1  =  2an + 1

or
              2an  =  n

                a  =  1/2
and thus

                b  =  1 - a  =  1/2

Therefore

              SUM  =  1/2 n^2 + 1/2 n

and this is the same as

                       n(n+1)
              SUM  =  -------
                         2

Thus, WITHOUT KNOWING IN ADVANCE the exact formual for the sum, we
were nonetheless able to FIND IT AND PROVE IT simply by guessing,
not the exact formula but rather only its general form (quadratic).
The method then determined the exact values of the coefficients,
as part of the inductive method of proof.

Had we chosen c = 1 instead of c = 0 (perhaps in order to get a + b =
0) then we'd have found n+1 = 2an (instead of n+1 = 2an + 1 as in (*)
above).  It would follow that a = (n+1)/2n = 1/2 + 1/2n which is not a
constant, and thus the choice of c = 1 cannot give us a solution of
the desired form.  At this point we should then go back and chose
another value for c, such as c=0 as we did above.  Does this mean that
there might still be other solutions that do not have a=constant?
Well, once we do find a solution where a=constant, then any other
solutions must be equal to that one (even if in a different form),
since all solutions must be equal to the original SUM.  

Also note that we could have started the induction at n=0, and found
that d=0 right away, since n=0 means that there are no terms at all so
the sum is 0.  Finally, if we feel our original guess is too general
(too many parameters to worry about) we could have strengthened (and
simplified) it at the beginning by a little more computing. For example 
for n equal to 2, we get the following condition on a, b, and c:

 1 + 2 = 3 = a 2^2 + b 2 + c = 4a + 2b + c

which gives us, together with  c = 1 - a - b,

 2 = 3a + b

a relation between only a and b: b = 2 - 3a.  We then could use, 
instead of the original guess an^2 + bn + c, the more specific 
guess an^2 + (2 - 3a)n + (1 - a - (2 - 3a)), i.e.,

          SUM = an^2 + (2 - 3a)n + 2a - 1

This we can also prove by induction, first the base case and then
the inductive step, finding that for the inductive step to work,
we need a = 1/2 as before.

============================================




Some further examples of induction proofs:

THEOREM: Let X be a set with n elements.  Then the powerset of X,
P(X), has 2^n elements.

PROOF (by induction): If n=0 (base case) then X is empty, and P(X) has
only one element. Since 1 = 2^0, this case is done.

Now suppose (IH) that the theorem is true for all sets with n=k
elements; we must show that it also holds for sets with k+1 elements.
So let X be a set with k+1 elements.  How do we get a set with k
elements from X,so we can apply the IH?  We remove one element, say b,
from X, leaving a smaller set Y with k elements: X = Y u {b}. Then by
the IH, P(Y) has exactly 2^k elements.  Notice that all these 2^k
subsets of Y are also subsets of X, and that none of them contains the
missing element b. The *other* subsets of X, ie the ones *not* among
the 2^k subsets of Y, are precisely those that *do* contain b -- how
many of those are there?  Well, each such subset is of the form {b} u
S where S consists of elements other than b, ie S is a subset of Y,
and there are 2^k such S's. So there are 2^k subsets of X that contain
b, and since there are also 2^k that do not, then the total number is
the sum: 2^k + 2^k = 2^(k+1), and we are done.


THEOREM: Let T be a binary tree with height h.  Then T has at most
2^(h+1) -1 nodes.

PROOF (by strong induction): If h=0 (base case) then T has only one
node (the root) and 1 = 2^(0+1) - 1.

Now suppose (IH) that the theorem is true for all binary trees of
height h <= k; we must show that it also holds for trees of height
h=k+1.  So let T be a tree of height k+1.  How do we get a tree of
height k from T, so that we can apply the IH? Here is the trick:
remove the root from T, which then leaves two subtrees T_left and
T_right. Each of these has height less than the height of T, hence at
most k, so the IH applies to them: n_left <= 2^(k+1)-1 and n_right<=
2^(k+1)-1. Let the total number of nodes in T be n, so that n = n_left
+ n_right + 1.  Then n <= 2 * 2^(k+1) -1 -1 +1 = 2^(k+1) - 1, and we
are done.
\end{verbatim}
\end{document}
