we can break this problem into different cases:
Now first assume we already build the string of length n-1 and then,
- we want to add 0 at the end of it (we are concatenating at right end), we know adding a zero can’t increase the number of string with consecutive ones.
- so $a_{n-1}$ is the number of strings of length n-1 with 2 consecutive one, we then add a 0, this number remains the same.
-
- we want to add a 1 at the end, here we need to be little careful about whether last element of string of length n-1 is 1 or 0, so we have to analyze last 2 bits instead of 1,
- for 2 bits, cases for 00 and 10 are covered in case 1 (adding 0 at the end).
- we left with two case 01 and 11
- adding 01 at the end of a string of length can’t add any extra consecutive 1’s, so this gives $a_{n-2}$ possible strings
- lastly we are adding 11, which is itself a pair of consecutive ones, so irrespective of what we have in those n-2 bits, adding 11 make all of them a string with two consecutive 1’s, So there are $2^{n-2}$ possible string of length n-2, and we are adding 11 at the end, so this case gives $2^{n-2}$ strings with two consecutive 1’s
Adding all together, $a_{n}$ will be:
- $a_{n-1}$ (adding 0 at the end.)
- $a_{n-2}$ (adding 01 at the end)
- $2^{n-2}$ (adding 11 at the end)
$a_{n} = a_{n-1} + a_{n-2} + 2^{n-2}$
(All these cases are disjoint, string from case 1(adding 0) and case 2(adding 01) are disjoint because of last bit is different, similarly case1(adding 0) and case 2(adding 11) are different, case 2 and 3 are disjoint by their second last bit)
A similar kind of analysis can be done for all variant of this problem,
For 2 consecutive 0’s everything remains same, just replace 0 with 1, and 1 with 0.
For no consecutive 0’s ( or for no consecutive 1’s, after doing same replacement here as well)
it goes as follows: (explaining for no consecutive 0’s)
we get string of length n-1 by recursion, we can add 1 at the end with worrying about anything, because adding 1 can never generate consecutive ones, so we get $a_{n-1}$ for string of length n-1,
for adding 0 we have to be careful, lets move to last two bit,
last two bits can be 10, 01,11 ( it can’t be 00, because that is generating consecutive 0’s)
01, 11 both are covered in previous case(adding 1 at last bit)
we left with only one possible way, 10.. this case gives $a_{n-2}$
we are done as we have exploited all the possible cases,
therefore for no consecutive 0’s
$a_{n} = a_{n-1} + a_{n-2}$