Find the number of words recursively such that there is no palindromic suffix
2
1
$begingroup$
Given a set of distinct characters ${a_1, a_2, cdots , a_S}$ and a number $N$ , find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is no palindromic suffix in the word. In other words find the number of words such that for any $1<k leq N$ the last $k$ letters of the word shouldn't form a palindrome. This is certainly recursion. My initial idea was to consider last $k$ integers (for $k>1$ ) and make it a palindrome and ensure that any $j>k$ do not form a palindrome. Finally the answer would be $S^N - text{sum of our considerations}$ . But this way out seems to be quite tough.
combinatorics recursion formal-languages palindrome
...