Q: 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: Here is one way to do it in general for any graph:
The adjacency matrix for the graph is:
$$A=\begin{pmatrix}
0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 0 \\
\end{pmatrix}$$
what you want is $A_{1,1}^n$, This is already computable very fast, if you use logarithmic exponentiation on the matrix.
If you want to obtain a formula you can diagonalize the symmetric matrix:
$$\small{\begin{pmatrix}
1 & -1 & 1 & -1 & -1 &-1 \\
1 & -1 & 0 & 1 & 1 & 0 \\
1 & 0 & -1 & -1 & 0 & 1 \\
1 & 1 & -1 & 1 & -1 & -1 \\
1 & 1 & 0 & -1 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 1 \\
\end{pmatrix}
\begin{pmatrix}
2 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & -2 & 0 & 0\\
0 & 0 & 0 & 0 & -1 & 0\\
0 & 0 & 0 & 0 & 0 & -1\\
\end{pmatrix}
\begin{pmatrix}
\frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6} & \frac{1}{6}\\
\frac{-1}{6} & \frac{-1}{3} & \frac{-1}{6} & \frac{1}{6} & \frac{1}{3} & \frac{1}{6}\\
\frac{1}{6} & \frac{-1}{6} & \frac{-1}{3} & \frac{-1}{6} & \frac{1}{6} & \frac{1}{3}\\
\frac{-1}{6} & \frac{1}{6} & \frac{-1}{6} & \frac{1}{6} & \frac{-1}{6} & \frac{1}{6}\\
\frac{-1}{6} & \frac{1}{3} & \frac{-1}{6} & \frac{-1}{6} & \frac{1}{3} & \frac{-1}{6}\\
\frac{-1}{6} & \frac{-1}{6} & \frac{1}{3} & \frac{-1}{6} & \frac{-1}{6} & \frac{1}{3}
\end{pmatrix}}$$
And now it is easy to recover a formula for $A_{1,1}^n$:
$f(n)=\frac{(2^n +2) + (-1)^n(2^n+2)}{6}$. So if $n$ is odd we have $f(n)=0$ and otherwise we have $f(n)=\frac{2^n+2}{3}$.

Note that your particular case is easier because you are working with a crown graph.
In a crown graph of size $2m$ the number of closed walks of length $n$ is  $0$ when $n$ is odd and equal to the number of sequences $1=a_1,a_2,\dots a_n=1$ such that $a_i\neq a_{i+1}$ and every $a_i$ belongs to $\{1,2,\dots, m\}$ when $n$ is even.
The recursion for the number of such sequences is clearly $f(2)=1$ and $f(n)=(m-1)^{n-2}-f(n-1))$. Which is clearly solved by $f(n)=\frac{(m-1)^{n-1}+(-1)^{n}(m-1)}{m}$
So the number of closed walks from a fixed vertex in a crown graph on $m$ vertices of length $n$ is equal to $\frac{(m-1)^n+(-1)^n(m-1)}{m}$ when $n$ is odd and zero otherwise.

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.
