recurrence relation of vertices on an hexagon I have the following question. 
Let there be an hexagon $ABCDEF$.

We'll define a legal route of $n$ steps across the hexagon, as wakling one step (either clockwise or counterclockwise) at a time.
So a route of $2$ legal steps would be for example walking from $A \to B \to C$ or from $A \to F \to A$. 
We will define $a(n)$ as the number of legal routes of $n$ steps that start and end at vertex $A$.
I need to find a recurrence relation for $a(n)$.
I know that the initial terms are $a(0)=1$, $a(2)=2$ and $a(4)=6$.
 A: Taking advantage of the present symmetries allows to reduce the number of variables from six to two, one of which then can be eliminated.
Denote by $A_m$ the number of ways to get from $A$ to $A$ in $m={n\over2}$ double-steps (two successive steps counted as one), and by $C_m$ the number of ways to get from $A$ to $C$ in $m$ double-steps. By symmetry $C_m$ is also the number of ways to get from $A$ to $E$ in $m$ double-steps. The quantities $A_m$ and $C_m$ satisfy the following recursion:
$$A_{m+1}=2A_m+2C_m,\qquad C_{m+1}=A_m+3C_m\ .\tag{1}$$
Proof. We arrive at $A$ after $m+1$ double-steps, if after $m$ double-steps we were at $A$ and did one of $A\to B\to A$ or $A\to F\to A$, or were after $m$ double steps at one of  $C$ or $E$ and came then to $A$ in one double-step. Similarly for the second recursion.$\qquad\square$
We then also have $$A_{m+2}=2A_{m+1}+2C_{m+1}\ ,\tag{2}$$
and eliminating $C_m$ and $C_{m+1}$ from $(1)$ and $(2)$ gives
$$A_{m+2}-5A_{m+1}+4A_m=0\ .$$
The characteristic polynomial of this difference equation is $\lambda^2-5\lambda+4=0$ with  zeros $4$ and $1$. We therefore obtain
$$A_m=c_14^m+c_2 \qquad(m\geq0)\ ,$$
and together witth $A_0=1$, $A_1=2$ this leads to
$$A_m={1\over3}(4^m+2)\ ,$$
so that your $a_n$ becomes $a_n=0$ if $n$ is odd and $a_n={1\over3}(2^n+2)$ if $n$ is even.
