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, .