Self-avoiding walks, the language of science, and Fibonacci numbers (Q1923411)

Consider the infinite graph with the pairs of integers in \(\{0,1\}\times\mathbb{Z}\) as vertices and edges of the form \(((0,i),(1,i))\), \(((0,i),(0,i+1))\) and \(((1,i),(1,i+1))\) for all \(i\in\mathbb{Z}\). A path of length \(n\) starting at \((0,0)\) is called a self-avoiding walk or saw. This paper is devoted to proving the following result: The number, \(a^{(2)}_n\), of \(n\)-step saws in the strip \(\{0,1\}\times[-\infty,\infty]\) is given by \(a^{(2)}_0=1\), \(a^{(2)}_1=3\), and for \(n>1\), by \(a^{(2)}_n=8F_n-{n\over 2}(1+(-1)^n)-2(1-(-1)^n)\).