Austria 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{array}{rl}{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{array}$$ 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{array}{rl}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{array}$$ 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}.$$