Explanation:
a) Given B(n) is the number of the length 'n' bit sequences which have no three consecutive 0s(i.e., they does not contain substring “000”)
Any bit string which has no 000 should have a 1 in at least one of the 1st three positions. Then, the n we will break all the bit strings by avoiding the 000 by when the 1st 1 occurs. i.e., each of the bit of string of the length of n will avoid 000 falls into the exactly any one of these cases:
1 is followed by the bit string of the length of (n-1) avoiding the 000.
01 is followed by some bit string of the length of (n-2) avoiding a 000.
001 which is followed by any bit string of the length(n-3) avoiding the 000.
Therefore, recurrence is
B(n)=B(n-1)+ B(n-2)+ B(n-3), with B(0)=1, B(1)=2, B(2)=4
Or
B(n)=B(n-1)+ B(n-2)+ B(n-3), with B(1)=2, B(2)=4, B(3)=7
b) Let the S(n)={1,2,3,…,n}. We will say that the subset A of S(n) is very good if A does not have any of the two integers that are consecutive.
For any k, let a(k) be a number of any good subsets of a S(k).
There are two types of good subsets of S(n).
Type 1 of good subsets of S(n) which contain the element n,
Type 2 of good subsets of S(n) which do not contain n.
We will first get an expression for a number of Type 1 of good subsets of the S(n) , where n≥2. This a subset does not contain n-1. So any Type 1 of the good subset of the S(n) is obtainable when adding n to good subset of the S(n-2) . Also, on adding n to a good subset of the S(n-2) , we always get a Type 1 good subset of the S(n). Thus there are exactly as many good Type 1 of subsets of S(n) as there is good subsets of S(n-2) . By the definition there are a(n-2) good subsets of S(n-2) .
A good subset of a S(n) is either Type 1 or Type 2. Thus the number of the good subsets of S(n) is a(n-2)+a(n-1)
We have therefore shown that a(n) = a(n-2)+a(n-1)
c). Here firstly see that if the n is not the multiple of a 3, then there will be no chance to tile the rectangle. And also if n is a multiple of a 3, then there may be two ways to tile the 1st three columns:
And the rest of tilling is the tilling of 2x(n-3) rectangle for which there are T(n-3).
So, the recurrence is
T(n )= {2T(n-3), with T(0)=1 if n=0(mod 3) or 0 else
We could use the base case T(3)=2
So, the following recurrence can be aslo equivalent to T(n)= 2T(n-3), with T(0)=1, T(1)=0,T(2)=0
Or
T(n)= 2T(n-3), with T(1)=0, T(2)=0,T(3)=2
d)A ternary string may be defined as a sequence of some digits, where each digit has either 0,1,or 2.
According to the problem given, we do not have a 2 anywhere after 0, and the dot which represents the binary string of length(n-1) with the property which we cannot use 2 anywhere after we use the 0.
Now for base case, we should note that any of the ternary string which has a length of 1 satisfies the given required property. Hence the recurrence is
T(1)=3
T(n)=2T(n-1)+2^(n-1)
