Chapter 2: Mathematical Preliminaries );! 61
respectively. As F o = 0, F I = 1, F~ =1, these are true. Hence there is basis
for induction. Assume P n and Qw So
(2.2)
(2.3)
Now.
= (F,~-l + F,~) + F"-lF,, + F,; + F"-lF,,
=F,;-l + F,~ + (F,,-l + F" )F" + F"F,,-l
=(F,~-l + F,;) + F,'~lF" + F"F,'-l
(by (2.3»)
This proves P n + l •
Also.
(By P' 1+1 and (2.3))
This proves Qn+l'
So. by induction (2.2) and (2.3) are true for all 11.
We conclude this chapter with the method of proof by contradiction.
2.5 PROOF BY CONTRADICTION
Suppose we want to prove a property P under certain conditions. The method
of proof by contradiction is as follows:
Assume that property P is not true. By logical reasoning get a conclusion
which is either absurd or contradicts the given conditions.
The following example illustrates the use of proof by contradiction and
proof by induction.
EXAMPLE 2.26
Prove that there is no string x in {a. b}* such that (L-r: = xb. (For the definition
of strings. refer to Section 2.3.)