# 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?

• Try working with the number of ways to reach each of the six points after $n$ steps (so six variables) - there is a left-right symmetry which will help. Sometimes it is easier to make a problem look more complicated before simplifying. This way you record and control all the data. – Mark Bennet Jan 19 at 10:12
• Since you have made the realisation that you need an even number of steps, you can also think about moving around the hexagon two steps at a time though. This reduces your problem to moving around a triangle, where you may choose not to move at each 'double-step'. You have to take care however, since there are two ways to choose not to move. – GossipM Jan 19 at 10:38