Prove the recursion for "Goosenish" palindromes 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.
 A: 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$.
A: 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.
