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}$