A type 1 sequence is a sequence with each term 0 or 1 which does not have 0, 1, 0 as consecutive terms. A type 2 sequence is a sequence with each term 0 or 1 which does not have 0, 0, 1, 1 or 1, 1, 0, 0 as consecutive terms. Show that there are twice as many type 2 sequences of length n+1 as type 1 sequences of length n.
Solution
Let S be the set of sequences length n and T the set of sequences length n+1 beginning with 0. Define f: S → T as follows. Let the m+1th term of f(s) be the same as the mth term if the mth term of s is 0 and different if the mth term of s is 1. It is clear that f is a bijection. [Define its inverse g by g(t) has 0 as its mth term iff the mth and m+1th terms of t are the same.] Also f(s) includes 0, 0, 1, 1 or 1, 1, 0, 0 iff s includes 0, 1, 0. Hence the number of type 1 sequences in S is the same as the number of type 2 sequences in T. The same result holds if we take T to be sequences which begin with 1.
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002