(a) How many length 3 strings over {a, b} are there?

(b) Let k 0. How many length-k strings over {a, b} are there? Simplify your answer as much as possible.

(c) Let k 0. How many length-k strings over {a, b} that start with b are there? Simplify your answer as much as possible.

(d) Let be an alphabet with || = d, and let k 0. How many length-k strings over are there? Simplify your answer as much as possible.

(e) Let be an alphabet with || = d, and let k 0. Prove by mathematical induction that the number of strings over of length less than or equal to k is equal to dk+11. Use your answer from (d) when formulating the problem.