5. 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)), e (denoting the empty sequence). For strings z and y over an alphabet, we denote by al the length of the sequence a, and by ry the concatenation of the two sequences z and y in that order. For each integer n 2 0, we define the strings tn and yn over the alphabet (0,1 as follows: o 0 and yo and for n 21, zn = Zn-lyn-l and Un = yn-1Zn-l. Prove the following statements using mathematical induction (a) For every n2 0, nn (b) For every n 2 0, xn and yn differ in every position. (c) For every n 2 0, r2n and y2n are palindromes. (A string x is a palindrome if the reversal sequence of z is identical to the sequence a.) (d) For every n 20, an contains neither the substring 000 nor the substring 111. (A string a is a substring of a string y if a is simply a contiguous subsequence of y.)