(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.
and that matches up with
and so on, not sure what to do next.