4. An alphabet is a non-empty finite set of symbols, and a string over the alphabet is a finite sequence of symbols of the alphabet. Some example strings over the binary alphabet {0,1} are: 1011 (for the sequence (1,0,1,1), 10 (for the sequence (1,0)), (denoting the empty sequence). For strings r and y over an alphabet, we denote by the length of the sequencer, and by ry the concatenation of the two sequences x and y in that order. For each integer n > 0, we define the strings In and Yn over the alphabet {0,1} as follows: Do = 0 and yo = 1, and for n > 1, n = {n-1 Yn-1 and yn = Yn-In-1. Prove the following statements using mathematical induction: (a) For every n > 0, 2n = lynl. (b) For every n > 0, 2, and yn differ in every position (c) For every n > 0, 22n and y2n are palindromes. (A string 2 is a palindrome if the reversal sequence of 2 is identical to the sequence x.) (d) For every n > 0, en contains neither the substring 000 nor the substring 111. (A string is a substring of a string y if x is simply a contiguous subsequence of y.) 5. Let be an alphabet. For a string over , the reversal of e, denoted by