Problem 3: Strings of length n are composed of the following strings: 1, 22, 33, 24, 43, 556 and 655. Let Sn be the number of strings of length n that can be formed in this way. (Note that So = 1, because the empty string satisfies the condition.) (a) Derive a recurrence relation for the numbers Sn. Justify it. (b). Let Pn be the number of strings of length n that can be formed from the given strings, considering that four l's cannot be next to each other. (The substring 1111 is not allowed.) Derive a recurrence relation for the numbers Pn. Justify it