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.
Let $\overline{q}$ denote the reversal of a string $q$. Given a word $w$ with a palindromic suffix, we may define $\text{LPS}(w)$ as the longest palindromic suffix. If $\text{LPS}(w)$ is not periodic, it has the structure $\overline{q}q$ or the structure $\overline{q}q$ ($|q|\geq 2$) with one of the central characters being removed (let us denote this as $\overline{q}q^{*}$), where $q$ is an aperiodic word. From the theory of necklace polynomials / Moebius inversion we know that the number of aperiodic words with length $\ell$ over an alphabet with $S$ symbols is given by $$A_{\ell,S}=\sum_{d\mid \ell}\mu\left(\frac{\ell}{d}\right)S^d $$ hence we have an explicit way of counting the strings with a $\text{LPS}$, according to it being a $(\overline{q}q)^m$ or a $(\overline{q}q^*)^m$. On the other hand we may also consider that
This leads to a much simpler recursion for counting the strings with an $\text{LPS}$:
$$ \left\{\begin{array}{rcl}P_\ell &=& S^{\ell-2}(S-1)+S P_{\ell-2}\\ D_\ell &=& S P_{\ell-1}\end{array}\right.$$
If my computation are correct, we have that the strings with length $n$ and a palindromic suffix are $ 2 S^{n-1} - S^{\lfloor n/2\rfloor}$.