Find the number of words recursively such that there is no palindromic suffix 
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. 
 A: 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


*

*If $\text{LPS}(w)$ has odd length, by removing or duplicating the central character of the $\text{LPS}$ we get a string with a palindromic suffix whose length is $|w|\mp 1$;

*If $\text{LPS}(w)$ has even length, by inserting a character in the middle of such $\text{LPS}$ the string $w$ with a periodic suffix is mapped into a string with a periodic suffix and length $|w|+1$.


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}$.
