ways to walk on a hexagon to return to same point with n steps 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?
 A: 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$.
A: 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.
