2026-03-26

Problem — 2026-03-26

Medium

Mediumcombinatorics

How many $5$ -letter strings using only $A$ and $B$ contain no three consecutive $A$ 's?

Enter an integer

Show solution

Let

a_n

be the count of valid

n

-letter strings. A valid string can start with

B

AB

, or

AAB

, each followed by a valid string. So

a_n = a_{n-1} + a_{n-2} + a_{n-3}

. With

a_1 = 2

a_2 = 4

a_3 = 7

a_4 = 7+4+2 = 13

a_5 = 13+7+4 = 24