CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 111
EXAMPLE 6.5 Consider six people, where any two of them are either friends or strangers. Show that there are
three of them which are either mutual friends or mutual strangers.
LetAbe one of the people. LetXconsist of those which are friends ofA, andYconsist of those which
are strangers ofA. By the Pigeonhole Principle, eitherXorYhas at least three people. SupposeXhas three
people. If two of them are friends, then the two withAare three mutual friends. If not, thenXhas three mutual
strangers. Alternately, supposeYhas three people. If two of them are strangers, then the two withAare three
mutual strangers. If not, thenXhas three mutual friends.
EXAMPLE 6.6 Consider fivelatticepoints(x 1 ,y 1 ),...,(x 5 ,y 5 )in the plane, that is, points with integer coor-
dinates. Show that the midpoint of one pair of the points is also a lattice point.
The midpoint of pointsP(a,b) andQ(c,d)is([a+c]/ 2 ,[b+d]/ 2 ). Note that(r+s)/2 is an integer ifrand
sare integers with the sameparity, that is, both are odd or both are even. There are four pairs of parities: (odd,
odd), (odd, even), (even, odd), and (even, even). There are five points. By the Pigeonhole Principle, two of the
points have the same pair of parities. The midpoint of these two points has integer coordinates.
An important application of the Pigeonhole Principle follows.
Theorem 6.7: Every sequence of distinctn^2 +1 real numbers contains a subsequence of lengthn+1 which is
strictly increasing or strictly decreasing.
For example, consider the following sequence of 10= 32 +1 numbers (wheren=3): 2, 1, 8, 6, 7, 5, 9, 4,
12, 3. There are many subsequences of lengthn+ 1 =4 which are strictly increasing or strictly decreasing; for
example,
2 , 6 , 9 , 12 ; 1 , 5 , 9 , 12 ; 8 , 6 , 5 , 4 ; 7 , 5 , 4 , 3.
On the other hand, the following sequence of 9= 32 numbers has no subsequence of lengthn+ 1 =4 which is
strictly increasing or strictly decreasing:
3 , 2 , 1 , 6 , 5 , 4 , 9 , 8 , 7.The proof of Theorem 6.7 appears in Problem 6.10.
6.6Recurrence Relations
Previously, we discussed recursively defined functions such as(a) Factorial function, (b) Fibonacci sequence, (c) Ackermann function.Here we discuss certain kinds of recursively defined sequences{an}and their solution. We note that asequence
is simply a function whose domain is
N={ 1 , 2 , 3 ,...} or N 0 =N∪{ 0 }={ 0 , 1 , 2 , 3 ,...]We begin with some examples.
EXAMPLE 6.7 Consider the following sequence which begins with the number 3 and for which each of the
following terms is found by multiplying the previous term by 2:
3 , 6 , 12 , 24 , 48 , ...It can be defined recursively by:
a 0 = 3 ,ak= 2 ak− 1 fork≥1ora 0 = 3 ,ak+ 1 = 2 ak fork≥ 0The second definition may be obtained from the first by settingk=k+1. Clearly, the formulaan= 3 ( 2 n)gives
us thenth term of the sequence without calculating any previous term.