MathDB
n-term Sequence

Source: USAMO 1996, Problem 4

October 22, 2005
inductionfunctionmodular arithmeticstrong inductioncombinatorics unsolvedcombinatorics

Problem Statement

An nn-term sequence (x1,x2,…,xn)(x_1, x_2, \ldots, x_n) in which each term is either 0 or 1 is called a binary sequence of length nn. Let ana_n be the number of binary sequences of length nn containing no three consecutive terms equal to 0, 1, 0 in that order. Let bnb_n be the number of binary sequences of length nn that contain no four consecutive terms equal to 0, 0, 1, 1 or 1, 1, 0, 0 in that order. Prove that bn+1=2anb_{n+1} = 2a_n for all positive integers nn.
Back to ProblemsView on AoPS