Discrete Mathematics: Elementary and Beyond

2.1 Induction 29

result we wanted to get, but after giving the argument once or twice, we
said “etc.” instead of further repetition. There is nothing wrong with this,
if the argument is sufficiently simple so that we can intuitively see where
the repetition leads. But it would be nice to have some tool at hand that
could be used instead of “etc.” in cases where the outcome of the repetition
is not so transparent.
The precise way of doing this is using induction, as we are going to
illustrate by revisiting some of our results. First, let us give a proof of the
formula for the number of subsets of ann-element set, given in Theorem
1.3.1 (recall that the answer is 2n).
As the Principle of Induction tells us, we have to check that the assertion
is true forn= 0. This is trivial, and we already did it. Next, we assume that
n>0, and that the assertion is true for sets withn−1 elements. Consider
a setSwithnelements, and fix any elementa∈S. We want to count the
subsets ofS. Let us divide them into two classes: those containingaand
those not containinga. We count them separately.
First, we deal with those subsets that don’t containa. If we deleteafrom
S, we are left with a setS′withn−1 elements, and the subsets we are
interested in are exactly the subsets ofS′. By the induction hypothesis, the
number of such subsets is 2n−^1.
Second, we consider subsets containinga. The key observation is that
every such subset consists ofaand a subset ofS′. Conversely, if we take
any subset ofS′, we can addato it to get a subset ofScontaininga.
Hence the number of subsets ofScontainingais the same as the number of
subsets ofS′, which is, by the induction hypothesis, 2n−^1. (We can exercise
another bit of mathematical jargon introduced before: The last piece of the
argument establishes a one-to-one correspondence between those subsets of
Scontainingaand those not containinga.)
To conclude: The total number of subsets ofSis 2n−^1 +2n−^1 =2· 2 n−^1 =
2 n. This proves Theorem 1.3.1 (again).

2.1.10Use induction to prove Theorem 1.5.1 (the number of strings of length
ncomposed ofkgiven elements iskn) and Theorem 1.6.1 (the number of per-
mutations of a set withnelements isn!).

2.1.11Use induction onnto prove the “handshake theorem” (the number of
handshakes betweennpeople isn(n−1)/2).

2.1.12Read carefully the following induction proof:

Assertion:n(n+1)is an odd number for everyn.

Proof:Suppose that this is true forn−1 in place ofn; we prove it

forn, using the induction hypothesis. We have

n(n+1)=(n−1)n+2n.