Problem 2.4. Consider an alphabet of $n$ letters, with which we will form words. We will say that a word contains a palindrome if a segment of that word, of more than one letter, reads the same forwards as backwards. For example, the word OLIMPIADAS contains the palindrome ADA. Given an integer $k$ greater than 2, determine how many words of length $k$ can be formed, with our alphabet of $n$ letters, that do not contain any palindrome of odd length.
Solution Problem 2.4 Observe that a word contains an odd-length palindrome if and only if it contains a palindrome of length 3. Therefore, we only need to count the words that do not contain a palindrome of length 3.

We can enumerate all the requested words as follows: for the first letter, we have $n$ possibilities. For the second letter, we also have $n$ possibilities. The third letter can be anything except the letter in position 1. Therefore, for the third letter, we have $n-1$ possibilities. The fourth letter can be anything except the one in position 2, so we also have $n-1$ possibilities. This way, we will reach the $k$-th letter, which can be anything except the one in position $k-2$, and thus there are also $n-1$ possibilities. Therefore, in total, there are $n^{2}(n-1)^{k-2}$ words that do not contain an odd-length palindrome.