In a proof by induction, we argue as follows: From Condition 1 we know that
the first k statements are true. Then Condition 2 tells us that P k+1 also must be
true. But now that we know that the first k + 1 statements are true, we can apply
Condition 2 again to claim that P k+2 must be true, and so on. We need not
explicitly continue this argument, because the pattern is clear. The chain of
reasoning can be extended to any statement. Therefore, every statement is true.
The starting statements P 1 , P 2 ,…P k are called the basis of the induction. The
step connecting P n with P n+1 is called the inductive step. The inductive step is
generally made easier by the inductive assumption that P 1 , P 2 ,…, P n are true,
then argue that the truth of these statements guarantees the truth of P n + 1 . In a
formal inductive argument, we show all three parts explicitly.
Example 1.5
A binary tree is a tree in which no parent can have more than two children. Prove
that a binary tree of height n has at most 2 n leaves.
Proof: If we denote the maximum number of leaves of a binary tree of height n
by l (n), then we want to show that l (n) ≤ 2 n .
Basis: Clearly l (0) = 1 = 2 0 since a tree of height 0 can have no nodes other than
the root, that is, it has at most one leaf.
Inductive Assumption:
Inductive Step: To get a binary tree of height n + 1 from one of height n, we can
create, at most, two leaves in place of each previous one. Therefore,
Now, using the inductive assumption, we get
Thus, if our claim is true for n, it must also be true for n + 1. Since n can be any
number, the statement must be true for all n.
the first k statements are true. Then Condition 2 tells us that P k+1 also must be
true. But now that we know that the first k + 1 statements are true, we can apply
Condition 2 again to claim that P k+2 must be true, and so on. We need not
explicitly continue this argument, because the pattern is clear. The chain of
reasoning can be extended to any statement. Therefore, every statement is true.
The starting statements P 1 , P 2 ,…P k are called the basis of the induction. The
step connecting P n with P n+1 is called the inductive step. The inductive step is
generally made easier by the inductive assumption that P 1 , P 2 ,…, P n are true,
then argue that the truth of these statements guarantees the truth of P n + 1 . In a
formal inductive argument, we show all three parts explicitly.
Example 1.5
A binary tree is a tree in which no parent can have more than two children. Prove
that a binary tree of height n has at most 2 n leaves.
Proof: If we denote the maximum number of leaves of a binary tree of height n
by l (n), then we want to show that l (n) ≤ 2 n .
Basis: Clearly l (0) = 1 = 2 0 since a tree of height 0 can have no nodes other than
the root, that is, it has at most one leaf.
Inductive Assumption:
Inductive Step: To get a binary tree of height n + 1 from one of height n, we can
create, at most, two leaves in place of each previous one. Therefore,
Now, using the inductive assumption, we get
Thus, if our claim is true for n, it must also be true for n + 1. Since n can be any
number, the statement must be true for all n.