Suppose B is the set of bit strings recursively defined by: 001 ES Let an the number of bit strings in B of length n, for n 2. Determine a recursive definition for an, ie. determine a2, a3 and a recurrence relation. Make sure to justify your recurrence relation carefully. In particular, you must make it clear that you are not double-counting bit strings. Find a closed form solution for the sequence an from the previous prob- lem using the method for solving linear, homogeneous, constant-coefficient recurrence relations given in the lecture. Formulate a principle of induction that is suitable for proving a closed form a-f(n) for a sequence defined by two initial values a2 and a3, and a two-step recurrence an+2-g(an+i,an) for n 22. You do not have to prove the correctness of this principle. Apply it to prove that your closed form from the previous part is correct