Define the strings Fn (n 1) as follows:

Thus, for example, we find F3 = 10, F4 = 101, and so on.

(a) Prove that no Fi contains either 00 or 111 as a substring.

(b) Guess the relationship between FiFi+1 and Fi+1Fi, and prove your guess by induction .