1. Determine a recursive formula for the number of n bit binary strings that have the substring 10. How many such strings of length 8 exist? Determine a closed form for the number of n bit binary strings which have the substring 10.
2. Determine a relationship in the Fibonacci sequence and prove it.