Question: There is a colony of gnats who all wear hats. Each gnat wears a green, white, or red hat (they are Italian gnats). Moreover, a single gnat wears a green or red hat, and a partnered gnat wears a white hat-and partnered gnats always hold hands when they fly. Gnats often line up while flying.
(a) How many different hat-color strings are possible for two gnats with hats flying in a line?
(b) How many different hat-color strings are possible for three gnats with hats flying in a line?
(c) Consider the sequence gn of hat-color strings for n gnats with hats flying in a line. Write a recurrence and find a closed form for gn.