0

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

Community
  • 1
Samuel
  • 201

1 Answers1

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.

Ross Millikan
  • 374,822
  • 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,.... . – Samuel Dec 18 '12 at 14:54
  • 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}$ – Ross Millikan Dec 18 '12 at 15:28