Mathematical Induction 53
(Inductive step) Let n > no. Show that if n E T, then n + 1 e T. Since n > 1, n + 1 >
- Assume for n that
F1 +k F3 +t.. + F2n-1 = F2n - I
and prove that
F 1 + F 3 + ... + F2n-1 + F 2 (n+l)-l = F 2 (n+l) - 1
The required computation is
F1 + F 3 + • • + F 2 n- 1 + F 2 (n+l)-i
= (F 1 ± F 3 + + F2n-l) + F 2 (n+1)-1 (making the formula for n clear)
= F 2 n - 1 + F 2 (n,+I)- (using the inductive hypothesis)
= (F 2 n + F 2 (n+l)) - 1 (rearranging terms)
= F2n+ 2 - 1 (using the definition of F2z,+2)
= F 2 (n+l) - 1
Therefore, n + 1 E T.
By the Principle of Mathematical Induction, T = {n e N : n > 1). E
1.74 Application: Size of a Power Set
The next result was referred to in the discussion of computer switches in Section 1.3.4 and
will be proved several times in the book using several different ideas. Recall that 2(X),
the power set of X, is the set of all subsets of X.
Theorem 2. (Size of a Power Set) Let X be any finite set with n elements. Then, 2(X)
has 2' elements.
The proof of Theorem 2 can be proved by induction on the number of elements in
X. First, we prove an auxiliary result called a lemma. A lemma is the same as a theorem,
except that the result is not particularly important in its own right but only gives a step in
another proof. Just as procedures divide programs into manageable parts, lemmas are tools
for dividing a proof into smaller, more comprehensible pieces.
Lemma 1: Let X be any set, and let b ' X. If X has (exactly) n subsets, then X U [b}
has exactly 2n subsets.
Proof. List the subsets of X:
S 1 , S 2 , S 3 .,.... Sn
