A self-avoiding rook walk on a chessboard (a rectangular grid of squares) is a path traced by a sequence of rook moves parallel to an edge of the board from one unit square to another, such that each begins where the previous move ended and such that no move ever crosses a square that has previously been crossed, i.e., the rook's path is non-self-intersecting.

Let \( R(m, n) \) be the number of self-avoiding rook walks on an \( m \times n \) ( \( m \) rows, \( n \) columns) chessboard which begin at the lower-left corner and end at the upper-left corner. For example, \( R(m, 1) = 1 \) for all natural numbers \( m \); \( R(2, 2) = 2 \); \( R(3, 2) = 4 \); \( R(3, 3) = 11 \). Find a formula for \( R(3, n) \) for each natural number \( n \).
Let $r_{n}=R(3, n)$. It can be checked directly that $r_{1}=1$ and $r_{2}=4$. Let $1 \leq i \leq 3$ and $1 \leq j$; let $(i, j)$ denote the cell in the $i$ th row from the bottom and the $j$ th column from the left, so that the paths in question go from $(1,1)$ to $(3,1)$.

Suppose that $n \geq 3$. The rook walks fall into exactly one of the following six categories:

(1) One walk given by $(1,1) \rightarrow(2,1) \rightarrow(3,1)$.

(2) Walks that avoid the cell $(2,1)$: Any such walk must start with $(1,1) \rightarrow(1,2)$ and finish with $(3,2) \rightarrow (3,1)$; there are $r_{n-1}$ such walks.

(3) Walks that begin with $(1,1) \rightarrow(2,1) \rightarrow(2,2)$ and never return to the first row: Such walks enter the third row from $(2, k)$ for some $k$ with $2 \leq k \leq n$ and then go along the third row leftwards to $(3,1)$; there are $n-1$ such walks.

(4) Walks that begin with $(1,1) \rightarrow(2,1) \rightarrow \cdots \rightarrow(2, k) \rightarrow(1, k) \rightarrow(1, k+1)$ and end with $(3, k+1) \rightarrow (3, k) \rightarrow(3, k-1) \rightarrow \cdots \rightarrow(3,2) \rightarrow(3,1)$ for some $k$ with $2 \leq k \leq n-1$; there are $r_{n-2}+r_{n-3}+\cdots+r_{1}$ such walks.

(5) Walks that are the horizontal reflected images of walks in (3) that begin with $(1,1) \rightarrow(2,1)$ and never enter the third row until the final cell; there are $n-1$ such walks.

(6) Walks that are horizontal reflected images of walks in (5); there are $r_{n-2}+r_{n-3}+\cdots+r_{1}$ such walks.

Thus, $r_{3}=1+r_{2}+2\left(2+r_{1}\right)=11$ and, for $n \geq 3$,

$$
\begin{aligned}
r_{n} & =1+r_{n-1}+2\left[(n-1)+r_{n-2}+r_{n-3}+\cdots+r_{1}\right] \\
& =2 n-1+r_{n-1}+2\left(r_{n-2}+\cdots+r_{1}\right)
\end{aligned}
$$

and

$$
r_{n+1}=2 n+1+r_{n}+2\left(r_{n-1}+r_{n-2}+\cdots+r_{1}\right).
$$

Therefore

$$
r_{n+1}-r_{n}=2+r_{n}+r_{n-1} \Longrightarrow r_{n+1}=2+2 r_{n}+r_{n-1}
$$

Thus

$$
r_{n+1}+1=2\left(r_{n}+1\right)+\left(r_{n-1}+1\right),
$$

whence

$$
r_{n}+1=\frac{1}{2 \sqrt{2}}(1+\sqrt{2})^{n+1}-\frac{1}{2 \sqrt{2}}(1-\sqrt{2})^{n+1},
$$

and

$$
r_{n}=\frac{1}{2 \sqrt{2}}(1+\sqrt{2})^{n+1}-\frac{1}{2 \sqrt{2}}(1-\sqrt{2})^{n+1}-1.
$$