Question

For problems 1-4: a set S of bitstrings is recursively defined by:

- 1 is in S.

- if b is in S, so are 0b, 11b and 10b.

Let aₙ be the number of bitstrings in S of length n.

3. Express aₙ in terms of aₙ₋₁ and aₙ₋₂ for n ≥ 2. (Hint: you should get a homogeneous, linear, constant-coefficient recurrence relation with integer characteristic values.) Find the general solution of the recurrence. [6 pts]

4. Use the initial conditions you found in 1. to find a closed-form solution for aₙ . Verify that your a₃ is consistent with your result from part 2, i.e. count the bitstrings you obtained in part 2, and show that you get the same number from your closed-form solution. [4 pts]

Answer 1

3) because for each string of length n-2, we can either append 11 or 10 (according to the recursive definition) and for each string of length n-1, we can only append 0

We also have (only string in S of length 2 is 01)

3)

So

The general solution is

Initial conditions imply and

So

Solving this, we get

So that