, 2010

Let $a_k$, $b_k$ and $c_k$ be the number of possible paths leading from $(0,0)$ to $(k,0)$, $(k,1)$ and $(k,2)$ respectively. It is obvious that $a_0 = 1$, $b_0 = 0$ and $c_0 = 0$ hold. Furthermore, for $k \ge 1$ we have the recursive equations
$$\begin{aligned} c_k &= b_{k-1} + c_{k-1}, \\ b_k &= a_{k-1} + b_{k-1} + c_k \text{ and} \\ a_k &= a_{k-1} + b_k. \end{aligned}$$
From the first equation, we obtain $b_m = c_{m+1} - c_m$ for $m \ge 0$. Substituting in the second equation therefore yields
$$a_m = c_{m+2} - c_{m+1} - c_{m+1} + c_m - c_{m+1} = c_{m+2} - 3c_{m+1} + c_m$$
for $m \ge 0$, and substitution in the third equation finally yields
$$c_{m+2} - 3c_{m+1} + c_m - (c_{m+1} - 3c_m + c_{m-1}) - (c_{m+1} - c_m) = c_{m+2} - 5c_{m+1} + 5c_m - c_{m-1} = 0$$
for $m \ge 1$. The characteristic equation of the recursion is $q^3 - 5q^2 + 5q - 1 = 0$, and since $q^3 - 5q^2 + 5q - 1 = (q-1)(q^2 - 4q + 1)$, the roots of the characteristic equation are $q_1 = 1$, $q_2 = 2 + \sqrt{3}$ and $q_3 = 2 - \sqrt{3}$.
It follows that the required values are given by expressions of the form $c_n = A + B \cdot (2+\sqrt{3})^n + C \cdot (2-\sqrt{3})^n$. Since we know $c_0 = c_1 = 0$ and $c_2 = 1$, we obtain the system of equations
$$\begin{aligned} A + B + C &= 0 \\ A + (2 + \sqrt{3})B + (2 - \sqrt{3})C &= 0 \\ A + (7 + 4\sqrt{3})B + (7 - 4\sqrt{3})C &= 1. \end{aligned}$$
Solving this system of equations yields $A = -\frac{1}{2}$, $B = \frac{1}{4} - \frac{\sqrt{3}}{12}$ and $C = \frac{1}{4} + \frac{\sqrt{3}}{12}$, and the number of possible paths is therefore given by the expression
$$c_n = -\frac{1}{2} + \frac{(3 - \sqrt{3})(2 + \sqrt{3})^n}{12} + \frac{(3 + \sqrt{3})(2 - \sqrt{3})^n}{12}.$$