4. In a certain language, there are n letters. A group of letters (written in sequence) is a word if and only if no two identical letters are separated by two identical letters. Determine the number of all words of maximum length.

(K. Černeková)
Solution. Apparently, no word can contain four identical letters. The maximum possible length of a word in the considered language is therefore $3 n$ (a group of $n$ triplets of the same letters in a row is clearly a word). At the same time, it is clear that for $n=1$ there is only one word of length 3.

Let $n \geqq 2$.