According to Wikipedias there are 286 different Korean family names used in South Korea (using 2015 data). Of these, 274 consist of a single character, while 12 consist of two characters.

Let fn be the number of strings of South Korean family names in which each name is from the list of 286 names mentioned above, and the entire string consists of exactly n characters. Notes and clarifications:

The number of names in a string of n characters will also equal n only if every name in the string has just one character. The string will have

There are no separators (such as commas) in the strings. They consist of sequences of charac- ters, with nothing else.

An example string of three characters: \"27\" (using Hangul; in Hanja, it would be J\"), which consists of two names: the rare two-character family name \" ? (Mangjeol) followed by the one-character family name 7 (Kim) which is the most common of all.

(a) Find fi and good upper bounds for f2 and $3.

(b) Give (with justification) an expression for an upper bound for fr in terms of fn-1 and fn-2, that works for all n > 3.

(c) Prove, by induction on n, that fn