Let $a_{n}$ be the number of ways to go from $O$ to any (fixed) other vertex in exactly $n$ steps (well-defined by symmetry), and $b_{n}$ be the number of ways to go from $O$ to $O$ in exactly $n$ steps; we are interested in calculating $b_{2003}$. It's clear that $a_{n+1}= 2a_{n}+b_{n}$ and that $b_{n+1}= 6a_{n}$, with initial values $a_{0}= 0$ and $b_{0}= 1$. Then $a_{n+1}= 2a_{n}+6a_{n-1}$ so $a_{n}= a w^{n}+bz^{n}$ where $w, z$ are roots of $x^{2}-2x-6 = 0$. Then $a+b = a_{0}= 0$ and $aw+bz = a_{1}= 1$, and everything beyond this point is going to be just a lot of arithmetic that I don't want to do

JBL wrote: Let $a_{n}$ be the number of ways to go from $O$ to any (fixed) other vertex in exactly $n$ steps (well-defined by symmetry), and $b_{n}$ be the number of ways to go from $O$ to $O$ in exactly $n$ steps; we are interested in calculating $b_{2003}$. It's clear that $a_{n+1}= 2a_{n}+b_{n}$ and that $b_{n+1}= 6a_{n}$, with initial values $a_{0}= 0$ and $b_{0}= 1$. Then $a_{n+1}= 2a_{n}+6a_{n-1}$ so $a_{n}= a w^{n}+bz^{n}$ where $w, z$ are roots of $x^{2}-2x-6 = 0$. Then $a+b = a_{0}= 0$ and $aw+bz = a_{1}= 1$, and everything beyond this point is going to be just a lot of arithmetic that I don't want to do you are right, i think thanh you very much, your solution is very nice.

JBL wrote: $a_{n+1}= 2a_{n}+b_{n}$ Can someone explain a bit how did this come ? (only a bit hint please)

bump $^2$

hint