ways to walk on a hexagon to return to same point with n steps

Question

So I have an hexagon and I start at point 1 and I can only move right or left, I need to find the formula to reach the same point within n steps, Assuming I have an odd number of steps allowed, I can't ever return to the point.
But assuming I have even steps, I'm not sure how do I even think about it, I divided by two because I can go from 1>>2 or from 1>>6 so it's easier to just look at it as if i started with 1 step right.
This means that if the sequence is $ a_n $and I took a step right now i have $ a_{n-1}$ steps to come back. how do I go on from here?

Answer 1

Another approach:

While the situation is simple enough to describe it the way you did, I think the context of a walk on a graph naturally arises here: your graph is the (undirected) $6$-cycle. Let $A$ be its adjacency matrix, finding the number of ways to start from a given point $i$ and end at $i$ in $n$ steps is just the number of paths with length $n$ from $i$ to $i$. That number is given by computing $B = A^n$ and looking at $b_{ii}$.

Here $A$ is known: $$A=\begin{bmatrix} 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{bmatrix}$$

$A$ is diagonalisable, making it possible to find a "simple" closed form for $A^n$. In the end, the result you are looking for is: $$\frac{1}{6}\left (2(1+(-1)^n) + 2^n + (-2)^n \right)$$

However, as you noticed that for odd $n$, the result is always $0$, you can spare yourself some work and look directly at $A^2$ and find that the formula is $\frac{2^n + 2}{3}$ for even $n$.

Answer 2

I think I have a solution (although not a closed-form) for the general $N$-gon. Suppose we write out our sequence of moves as a list of $n$ letters, either $L$ or $R$ (for left and right). We want to count the number of possible lists of length $n$ where the number of $L$ exceeds the number of $R$ by a multiple of $N$.

This is done by choosing $k$ of these steps to be $L$ moves, such that the difference between $k$ and $n-k$ is an integer multiple of $N$. Hence, the total number of moves is $$\sum_{k\in S}\binom{n}{k}$$ where $S=\{0\leq k\leq n:n-2k\in N\mathbb{Z}\}$, which we can rewrite as $$k=\frac{n+mN}{2}$$ for all integers $|m|\leq n/N$. A closed form for this sum would clearly be desired however.