The problem
Imagine someone moving across a path laid out on a 2D grid:
The white tiles are the path; the surrounding red tiles are, say, deadly lava. They repeatedly move randomly north, east, south, or west, with equal probability, and have to make it from the Start tile to the End tile without stepping onto the lava.
What is the probability $p(n)$ that they succeed on an $n$-square-long path ($n=5$ is shown above)?
What I’ve tried
Number the tiles $1, \dots, n$, so that we’re walking from $1$ to $n$.
Call $a_k$ the probability we succeed when starting at the $k$-th tile. Clearly, $a_n = 1$, and we’re interested in the value of $a_1$.
From the $k$-the tile, there’s a 25% chance we move back to tile $k-1$, a 25% chance we move forward to tile $k+1$, and a 50% chance we step north or south onto a red tile and lose. So $a_k = \frac 14 \left( a_{k-1} + a_{k+1} \right)$, where $a_0 = 0$.
Putting the equations for $a_1, \dots, a_{n}$ in a matrix system gets us:
\begin{equation} \newcommand{\mof}{-1/4} \begin{bmatrix} 1 & \mof & 0 & \dots & 0 & 0 & 0 \\ \mof & 1 & \mof & \dots & 0 & 0 & 0 \\ 0 & \mof & 1 & \dots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & \mof & 0 \\ 0 & 0 & 0 & \dots & \mof & 1 & \mof \\ 0 & 0 & 0 & \dots & 0 & \color{red}0 & 1 \\ \end{bmatrix} \begin{bmatrix} a_1 \\ a_2 \\ a_3 \\ \vdots \\ a_{n-2} \\ a_{n-1} \\ a_n \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 0 \\ 1 \end{bmatrix} \tag{1} \end{equation}
I wrote some Mathematica code to solve this system for a given $n$ and give the value of $a_1$:
p[n_] :=
LinearSolve[
Table[If[x == y, 1,
If[y == n, If[x == n,1,0],
If[Abs[x - y] == 1, -1/4, 0]]],
{y, 1, n}, {x, 1, n}],
Table[If[x == n, 1, 0], {x, 1, n}]
][[1]]
The first few values $p(1), p(2), \dots$ are $$ \frac11, \frac1{4}, \frac1{15}, \frac1{56}, \frac1{209}, \frac1{780}, \dots, $$ the inverses of A001353 in the OEIS, which suggests a closed form:
$$p(n) = \frac{2 \sqrt{3}}{\left( 2 + \sqrt{3} \right)^n - \left( 2 - \sqrt{3} \right)^n}$$
But I’m not sure how to get there. I doubt there’s a nice way to solve a system like $(1)$ by hand. Maybe a combinatoric approach yields this formula without taking a detour through solving a system.