0
$\begingroup$

I know in this post "Recurrence relation for number of ternary strings that contain two consecutive zeros" Pat wrote "$a_n = a_{n-1} + a_{n-2} + 2^{n-2}$".

But I cannot understand how the $2^{n-2}$ appear. If the rightmost characters are 00, removing the "00" will get the string of n-2. The remaining string can be "01" "10" or "11"'s combination. Why the cardinality of this group is $2^{n-2}$?

1 Answers 1

0

If the rightmost characters are $00$, you don't care what comes before, you will have two consecutive zeros. So the first $n-2$ bits can be anything, giving $2^{n-2}$ possibilities.

  • 1
    @Samuel: No, it takes each bit separately, except for the last two. It says the string can end in $00, 01, 10, 11$. If it ends in $00$ it is acceptable regardless of what came before-that is the $2^{n-2}$. If it ends in anything else, it must have been acceptable before, or have the $00$ come from the addition. Adding a $1$ can never make a string acceptable, so you can add it to the end of $a_{n-1}$ strings. We still haven't accounted for the ones that end in $10$, and that is the $a_{n-2}$2012-12-18