Problem 1728

The answer is $\frac{7 - \sqrt{7}}{14}(1 + \sqrt{7})^{2003} + \frac{7 + \sqrt{7}}{14}(1 - \sqrt{7})^{2003}$.

For each integer $n \ge 0$, let $a_n$ be the number of paths of length $n$ starting at $O$ and terminating at $O$. Also, let $b_n$ be the number of paths of length $n$ starting at $O$ and terminating at $A$. By symmetry, $b_n$ is also the number of those paths terminating at any of $B, C, D, E, F$.

To count $a_n$ for $n \ge 1$, the $(n-1)$$\text{st}$ step must terminate at one of $A, B, C, D, E, F$. For each of these $6$ points, there are $b_{n-1}$ paths terminating at that point. This gives a total of $6b_{n-1}$ paths. In other words, we have
$$a_n = 6b_{n-1}. \tag{1}$$
To count $b_n$ for $n \ge 1$, suppose the $n$$\text{th}$ step terminates at $A$. Then the $(n-1)$$\text{st}$ step may terminate at $B, F$ or $O$. If it is $B$ or $F$, then there are $b_{n-1}$ paths. If it is $O$, then there are $a_{n-1}$ paths. Therefore, we have
$$b_n = 2b_{n-1} + a_{n-1}. \tag{2}$$
Combining (1) and (2), we obtain
$$\frac{1}{6}a_{n+1} = b_n = 2b_{n-1} + a_{n-1} = \frac{1}{3}a_n + a_{n-1}.$$
This can be rewritten as $a_n = 2a_{n-1} + 6a_{n-2}$ for $n \ge 2$. The roots of the characteristic equation $\lambda^2 - 2\lambda - 6 = 0$ are $1 \pm \sqrt{7}$. Suppose $a_n = A(1 + \sqrt{7})^n + B(1 - \sqrt{7})^n$. Using the initial conditions $a_0 = 1$ and $a_1 = 0$, we solve
$$\begin{cases} A + B = 1, \\ A(1 + \sqrt{7}) + B(1 - \sqrt{7}) = 0. \end{cases}$$
This yields $A = \frac{7 - \sqrt{7}}{14}$ and $B = \frac{7 + \sqrt{7}}{14}$. Therefore, the answer is
$$a_{2003} = \frac{7 - \sqrt{7}}{14}(1 + \sqrt{7})^{2003} + \frac{7 + \sqrt{7}}{14}(1 - \sqrt{7})^{2003}.$$