Q4. (15 points) Given an alphabet with n characters. Let the characters be numbered from 1 to n, and let the frequency of character i be fi = for i=1,2,...,n 1, with the last character n having frequency fn = ns. For example, if n=6, then the frequencies of the first five characters are 1/2, 1/4, 1/8, 1/16, 1/32, respectively, and the frequency of the last character is 1/32. Answer the following questions: a) (5 points) Show that the frequencies of all characters sum to 1 (as they should) for any n. b) (5 points) Show what the huffman encoding is for each character. In building the encoding tree, the larger frequency child should be on the left, and if there are two groups of characters with the same frequency, the one with the smaller index should be on the left. c) (5 points) What is the expected number of bits per character? Let the encoding length of character i be denoted as li, then the expected or average number of bits for the encoding is computed as E-li fi. Use this formula to derive an closed form expression (for any n)