1996 USAMO Problems/Problem 4
Problem
An -term sequence
in which each term is either 0 or 1 is called a binary sequence of length
. Let
be the number of binary sequences of length n containing no three consecutive terms equal to 0, 1, 0 in that order. Let
be the number of binary sequences of length
that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that
for all positive integers
.
(proposed by Kiran Kedlaya)
Solution
Given any binary sequence , define
. The operator
basically takes pairs of consecutive terms and returns 0 if the terms are the same and 1 otherwise. Note that for every sequence
of length
there exist exactly two binary sequences
of length
such that
.
If does not contain the string 0, 1, 0,
cannot contain either of the strings 0, 0, 1, 1 or 1, 1, 0, 0. Conversely, if
does not contain the sequences 0, 0, 1, 1 or 1, 1, 0, 0,
cannot contain 0, 1, 0. There are
such
and
such
. Since each
corresponds with two
, there are twice as many such
as such
; thus,
.