Recursive (Counting) LinearRecursion Intermediate

Problem - 4277

How many different strings of length $10$ which contains only letter $A$ or $B$ contains no two consecutive $A$s are there?


Let $F_n$ be the number of such qualified strings.

  • If the $n^{th}$ letter is $B$, then there are  $F_{n-1}$ possibilities. 
  • If the $n^{th}$ letter is $A$, then the $(n-1)^{th}$ letter must be $B$. Thus, there are $F_{n-2}$ possibilities.

It follows that $F_n$ satisfies the following recursion when $n \ge 3$: $$F_n=F_{n-1}+F_{n-2}$$

Meanwhile, it is easy to compute that $F_1=2$, and $F_2=2^2-1=3$. Hence,

  • $F_3=2+3=5$
  • $F_4=5+3=8$
  • $F_5=8+5=13$
  • $F_6=13+8=21$
  • $F_7=21+13=34$
  • $F_8=34+21=55$
  • $F_9=55+34=89$
  • $F_{10}=89+55=\boxed{144}$

report an error