Prove the recursion for "Goosenish" palindromes

Question

Goosenish is a language well-known in the animal kingdom for its refined phonetics. Its alphabet consists of three letters: h (standing for a noisy honk); c (standing for an uncontrolled cackle); and a (standing for an angry-hiss). Goosenish is a wide language, and every string that uses at least one character in {h,c,a} is a word in Goosenish. Geese have a special fascination for words full of symmetries, such as palindromes.

A palindrome is a word that reads the same backwards as forwards. Examples of palindromes in Goosenish are cachhcac, c, and hhh; words such as hcca are not palindromes.

Let $S$ be the set of Goosenish palindromes, and for every such palindrome $p$, let $w(p)$ be the length of $p$. For example: $w(\text{cachhcac}) = 8$. Consider $\Phi_{S}(x)=\sum_{n \geq 0} a_{n} x^{n}$ the generating series of $S$ with respect to $w$.

I am trying to prove part a):

$a_{n}=3 \cdot a_{n-2}, \text { for } n \geq 3$

using a recursive relationship, but I am unsure of how to structure the proof.

---

Full question here.

Answer 1

To show that $a_n=3a_{n-2}$, note that if you have a palendrome of size $n$ and snip off the first and last letters, you are left with a palendrome of size $n-2$. This gives you a map from $n$ to $n-2$. To go from $n-2$ to $n$, convince yourself that it suffices to choose one of the 3 letters to then append to the beginning and end of the $n-2$ length palendrome. Show then that all length $n$ palendromes can be formed by this procedure when you start with all $n-2$ length palendromes, i.e. each palendrome of length $n$ uniquely corresponds to a palendrome of length $n-2$.

Part $b$ is then trivial induction.

Answer 2

The palindromic words are either

• odd length with either h, c or a as the central letter.

or

• even length with no central letter.

In both cases we can build a palindrome by successively putting pairs of h's, c's and a's either side of a smaller palindrome.

So, to start this "building" process we begin with either h, c or a or nothing $\epsilon$

$$\epsilon + h + c + a$$

the $+$s here indicate the logical "or". Let's refer to these as our "start letters".

Next we can build either a $2$ letter or $3$ letter palindrome by putting our start letters between any pair of h'a, c's or a's. Express this as

$$(\epsilon + h+c+a)\cdot(h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)$$

where the operation $\cdot$ is distributive just like multiplication but when we operate say $h\cdot c\boxed{\phantom{h}}c$ the result is the palindrome $chc$ i.e. the $\cdot$ operator says in this case "put a 'c' at either end of 'h'".

We add these new palindromes to our $0$ and $1$ letter palindromes

$$(\epsilon + h+c+a)+(\epsilon + h+c+a)\cdot(h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)$$

We have now formed all $0$, $1$, $2$ and $3$ letter palindromes but we want to build all palindromes so we need to add to the above result the $4$ and $5$ letter palindromes given by successive operation $\cdot$

$$(\epsilon + h+c+a)\cdot(h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)\cdot (h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)$$ $$=(\epsilon + h+c+a)\cdot(h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)^2$$

giving

$$\begin{align}(\epsilon &+ h+c+a)+(\epsilon + h+c+a)\cdot (h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)\\&+(\epsilon + h+c+a)\cdot(h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)^2\end{align}$$

continuing to build in this way we see that all palindromes are generated by

$$(\epsilon + h+c+a)\cdot\sum_{k\ge 0}(h\boxed{\phantom{h}}h+c\boxed{\phantom{h}}c+a\boxed{\phantom{h}}a)^k$$

Now, if we only care about the length of our palindromes and not the letter content then we can call each letter $x$ and let the indices on $x$ count word length. Also, instead of the objects $x\boxed{\phantom{h}}x$ we write $x^2$ and treat the operation $\cdot$ exactly as multiplication, then our generating function is the result

$$\begin{align}f(x)&=(1+x+x+x)\sum_{k\ge 0}(x^2+x^2+x^2)^k\\[1ex]&=(1+3x)\sum_{k\ge 0}3^kx^{2k}\\[1ex]&=(1+3x)\sum_{k\,\text{even}}3^{k/2}x^{k}\end{align}$$

this is our generating function with coefficient of $x^k$ given as $f_k$. This $f_k$ receives a contribution for every palindrome length $k$ and is therefore our required count. We could write

$$f(x)=\frac{1+3x}{1-3x^2}$$

since $(1-3x^2)^{-1}=\sum_{k\ge 0}3^kx^{2k}$ however we only desire the count $f_k$ of $k$ letter palindromes so we can simply write

$$\begin{align}f(x)&=(1+3x)\sum_{k\,\text{even}}3^{k/2}x^{k}\\[1ex]&=\sum_{k\,\text{even}}3^{k/2}x^k+3\sum_{k\,\text{even}}3^{k/2}x^{k+1}\\[1ex]&=\sum_{k\,\text{even}}3^{k/2}x^k+\sum_{k\,\text{odd}}3^{(k+1)/2}x^{k}\end{align}$$

hence

$$f_k=\begin{cases}3^{k/2}& \text{$k$ even}\\ 3^{(k+1)/2} &\text{$k$ odd}\end{cases}$$

The desired recurrence can be easily proved from this or by rearranging

$$\begin{align}&f(x)=(1+3x)(1-3x^2)^{-1}\\ \implies & f(x)=1+3x+3x^2f(x)\\ \implies & f_k=3f_{k-2}\end{align}$$

for $k\ge 2$.