(f) Implication: This operation is designated by the symbol → and is 0 if its
first operand is 1 and its second operand is 0; otherwise → is 1.
0.1.6 Fun da men tal Proof Tech niques
(a) Prin ci ple of Math e mat i cal Induc tion
Proof of induction is used to show that all elements of an infinite set have a
specified property. The proof by induction has two parts, (i) Induction step
(ii) Basis.
The induction step proves that for each i ≥1, if P(i) is true, then so is
P(i +1). The basis proves that P(1) is true. When both these parts are proved,
then for each i, P(i) is proved.
Let us illustrate the method of writing a proof by induction.
Basis: To prove that P(1) is true.
Induction Step: For each i ≥1, assume that P(i) is true and use this assumption
to show that P(i + 1) is true.
(b) Pigeon-hole Prin ci ple
If A and B are finite sets and |A| > |B|, then there is no one-to-one function from
A to B. i.e., If an attempt is made to pair off the elements of A (the “pigeons”)
with elements of B (the “pigeonholes”), sooner or later we will have to put
more than one pigeon in a pigeonhole.
By induction, the pigeonhole principle can be proved.
Ì Exam ple 0.1.36: A sack has 50 marbles of 4 different colours. Show
that there are at least 13 marbles of the same colour.
Solu tion
Since we need to partition the set of 50 elements (marbles) into 4 sets
(colours), according to the Pigeon-hole principle at least one of the sets (same
colour) has 50/4 = 13 elements (marbles). That is to say that at least 13
marbles have the same colour.
Ì Exam ple 0.1.37: Show that 2
3
n
n
>
for n ≥10 by Mathematical
Induction.
Proof: (i) Basis: For n = 10, 2
1024 10
10
3
=
>
(ii) Inductive Step: Assume 2
3
k
k
>
28
Theory of Automata, Formal Languages and Computation