Try this Random Walk in ANY lattice.

Start from a point, call it 0. Next step can be any points you were before or nearest neighbor of these points. Name the number of possible paths S(k) after k steps.

Same as above, but now you can go neighbors only. Name the number of possible paths N(k) after k steps.

Same as most Random Walk problems, same points with different orders are considered different paths. Say, in 1D, (0, -1, 1) and (0, 1, -1) are different.

Find ANALYTICAL relation between S(k) and N(k).

I solved it. Both S(k) and N(k) cannot be solved analytically, but the relation can.