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 Answer 1


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.

  • $\begingroup$ OK, I get it this method is divided the string as a two bits group. Because it is mutually independent, we can count the number of 00 n, then n-2, then n-4,.... . $\endgroup$
    – Samuel
    Commented Dec 18, 2012 at 14:54
  • 1
    $\begingroup$ @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}$ $\endgroup$ Commented Dec 18, 2012 at 15:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .