$a_n = 2^n - (a_{n-2} + a_{n-1})$

I have read this formula somewhere but don't know how its used here $a_n$ is the number of bit-strings of length $n$


closed as off-topic by Did, Shailesh, Leucippus, Namaste, N. F. Taussig Feb 1 '18 at 2:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Did, Shailesh, Leucippus, Namaste, N. F. Taussig
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Are you sure about the formula: $a_1=0$, $a_2=1$, $a_3=3$ and it doesn't hold? $\endgroup$ – asdf Jan 31 '18 at 22:13
  • $\begingroup$ @asdf Doesn't $a_3=4?$ Did you not count $000?$ $\endgroup$ – saulspatz Jan 31 '18 at 22:22
  • $\begingroup$ @saulspatz $000$, $001$, $100$. What is the fourth? $\endgroup$ – Clement C. Jan 31 '18 at 22:23
  • $\begingroup$ $001, 100, 000$ $\endgroup$ – asdf Jan 31 '18 at 22:23
  • $\begingroup$ @ClementC. You're right. I overlooked "consecutive". $\endgroup$ – saulspatz Jan 31 '18 at 22:26

The formula I get is this:



Consider all such strings of length $n\geq2$:

If the first entry of such string is $1$, then the first entry doesn't contribute with anything to the property "have at least $2$ consecutive $0$'s" since and thus we can pretend it doesn't exist. Hence the number of such strings that start with $1$ is $a_{n-1}$.

If a string starts with $01$, then again, we need $2$ consecutive $0$'s and the $01$ has no contribution, so we could just erase the first $2$ entries and get that the number of such sequences is $a_{n-2}$

Finally, if it starts with $00$, then it doesn't matter what the other $n-2$ entries are, since we already have the $2$ consecutive $0$'s.

Since these are all possible cases we are done.


This gives a general formula which looks quite ugly to me.

Hopefully this helps

  • $\begingroup$ It says it's the n-th Fibonacci number plus the n-th Lucas number, which is just $F_{n-1}+F_n+F_{n+1},$ which doesn't look so ugly to me, especially for the solution to a recurrence relation, but I guess ugliness is in the eye of the beholder. :-) $\endgroup$ – saulspatz Jan 31 '18 at 22:41

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