At times, we want to associate an ordering with the nodes at each level; in
such cases we talk about ordered trees.
Figure 1.2
More details on graphs and trees can be found in most books on discrete
mathematics.
Proof Techniques
An important requirement for reading this text is the ability to follow proofs. In
mathematical arguments, we employ the accepted rules of deductive reasoning,
and many proofs are simply a sequence of such steps. Two special proof
techniques are used so frequently that it is appropriate to review them briefly.
These are proof by induction and proof by contradiction.
Induction is a technique by which the truth of a number of statements can be
inferred from the truth of a few specific instances. Suppose we have a sequence
of statements P 1 , P 2 ,…we want to prove to be true. Furthermore, suppose also
that the following holds:
1. For some k ≥ 1, we know that P 1 , P 2 ,…, P k are true.
2. The problem is such that for any n ≥ k, the truths of P 1 , P 2 ,…, P n imply the
truth of P n+1 .
We can then use induction to show that every statement in this sequence is true.