In each situation, write a recurrence relation, including base case(s), that describes the recursive structure of the problem. You do not need to solve the recurrence. Let B(n) be the number of length n bit sequences that have no three consecutive 0s (i.e., do not contain the substring "000"). Write a recurrence for B(n). Let S(n) be the number of subsets of {1, 2, ..., n} having the following property: no two elements in the subset are consecutive integers. The empty set with no elements should be included in your count. Write a recurrence for S(n). Say you are tiling a 2 times n rectangle with L-shaped tiles of area 3 (trominoes). To tile the rectangle is to cover it with tiles so that no tiles overlap and every cell is covered by some tile. Let T(n) denote the number of ways to tile the rectangle. Write a recurrence for T(n). A ternary string is like a binary string except it uses three symbols, 0, 1, and 2. For example, 12210021 is a ternary string of length 8. Let T(n) be the number of ternary strings of length n with the property that there is never a 2 appearing anywhere after a 0. For example, 12120110 has this property but 10120012 does not. Write a recurrence for T(n)