I'm solving the below quoted problem, and I was wondering if there's actually an analytical closed form solution?
Suppose there are $n$ connected squares in a straight line. You start in the first square. You can move to the right, or to the left of your first square, provided that your next step is still within the straight line of squares (e.g., in the first step you can't move left, and can only move right because moving left would make you go off-grid). You traverse $m$ steps. How many unique paths are there such that you return to square 1?
I don't think there's an analytical closed form solution. I think you can define a recursion based on states, where the states are represented by the number of steps remaining and the square we're on.
Define $T(i, j)$ to be the number of unique paths to reach square $i$ from square 1 using $j$ steps. Our boundary condition is $T(1, 0) = 1$. We also know that $T(i, j) = 0$ if $i$ is odd (even) and $j$ is even (odd).
Our recursion is: $$ T(i, j) = T(i + 1, j - 1) + T(i - 1, j - 1) $$
If any of the terms is out of bounds on the RHS, they just become zero. The recursion seems pretty simple, but is there a closed form solution for this?
Provided that $m\leq 2n$, the paths you are looking for are equivalent to Dyck words. There are various well-known ways to prove that the number of Dyck words is given by the Catalan numbers. So in this case: $C_{m/2} = \frac{1}{m/2+1}\binom{m}{m/2}$, ($m$ should obviously be even).