Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 0 down vote accepted

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.

share|cite|improve this answer
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
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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