(a) Find a recurrence relation and initial conditions for , the number of binary sequences of length n that do not contain 11.

(b) Explain why the number of subsets of that do not contain both and for equals . (Hint: appeal to a known 1-1 correspondence.)

(c) Prove that , where is the n-th Fibonacci number, defined by , and for . (One method that works is strong induction.)

So far, this is what I have.

(a)

for

with and

(b)

???

(c)

I know

and that matches up with

So,

and so on, not sure what to do next.