Here is my attempt:
- First there is $2 \cdot 2^{n-1}$ ways if string ends with $00$ or $11$.
- Second there are ways when string end with $10$ or $01$. So it will give us $a(n-1)$ ways to solve remaining part.
So the final answer would be $a(n) = 2^{n-1} + a(n-1)$. Am I right? If it possible could you explain this in your way, because I could not completely understand what I wrote. Thanks)
If a string of length $(n-1)$ has consecutive bits that are equal, then this will hold true for any string of length $n$ which is formed by appending a bit onto a valid string with length $n-1$. This is where the $2a(n-1)$ comes from (2 since we get to choose the last digit). Now to make sure we count all possible strings, we need to ensure that we count the strings who’s first $(n-1)$ bits do not fulfill the condition, but where the string fulfills the condition. The only such strings are those with first $n-1$ digits $$1010… \text{ and } 0101…$$ which end in a repeat so there are two such strings. So I think the solution should be $$a(n) = 2a(n-1) +2$$.