Consider the Huffman code for characters whose frequency follows the first term of Fibonacci sequence. Answer the following question:

(a) What is the optimal Huffman code for the following character frequencies?

a: 1, b: 1, c: 2, d: 3, e: 5, f: 8, g: 13, h: 21

Assume the smaller frequency child is always the left child.

(b) Generalize your answer to find the optimal code when all frequencies are the first n Fibonacci numbers.

(c) Prove that your solution is correct (hint: what property of Fibonacci numbers do you need to show to prove correnctness? Prove these properties.)