Question

Consider sequences that consist entirely of $A$ 's and $B$ 's and that have the property that every run of consecutive $A$ 's has even length, and every run of consecutive $B$ 's has odd length. Examples of such sequences are $AA,$ $B,$ and $AABAA,$ while $BBAB$ is not such a sequence. How many such sequences have length $14?$

Answer

Solution:

Let $a_n$ and $b_n$ count valid sequences of length $n$ beginning with $A$ and with $B.$ A sequence beginning with $A$ starts with $AA$ followed by any valid sequence of length $n - 2$ (possibly empty), so $a_{n+2} = a_n + b_n,$ where the empty sequence counts once. A sequence beginning with $B$ starts either with a single $B$ followed by a sequence beginning with $A,$ or with $BB$ followed by a sequence beginning with $B,$ so $b_{n+2} = a_{n+1} + b_n.$

Starting from $(a_1, b_1) = (0, 1)$ and $(a_2, b_2) = (1, 0),$ the pairs $(a_n, b_n)$ for $n = 3, 4, \ldots, 14$ are $(1, 2),\ (1, 1),\ (3, 3),\ (2, 4),\ (6, 5),\ (6, 10),\ (11, 11),\ (16, 21),\ (22, 27),\ (37, 43),\ (49, 64),\ (80, 92).$

The number of valid sequences of length $14$ is $80 + 92 = 172.$

2008 AIME I Problem 11

Solution:

Problem 11 in Other Years