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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\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 Dec 18 '12 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$ – Ross Millikan Dec 18 '12 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.