= Solution
Represent the <doubly infinite ladder graph> by $\mathbb Z\times\{0,1\}$, with horizontal <edges> between successive columns and a vertical rung at each column. An allowed <self-avoiding walk> is coded by a word in $R,V$. Two successive $V$ steps revisit the preceding <graph vertex> and are forbidden. Conversely, every word without consecutive $V$ steps is a <self-avoiding walk>: horizontal steps strictly increase the column, and a column is visited vertically at most once. This establishes a <bijection>, not merely an upper bound.
For the <directed ladder self-avoiding walk count>, $\sigma_0=1$, $\sigma_1=2$, and for $n\geq2$ a word either ends in $R$, or ends in $RV$. Removing that final block gives
$$
\sigma_n=\sigma_{n-1}+\sigma_{n-2},\qquad\boxed{\sigma_n=F_{n+2}}.
$$
Let $\varphi=(1+\sqrt5)/2$ be the <golden ratio>, and $\psi=(1-\sqrt5)/2$. The <Binet formula> for the <Fibonacci number> yields
$$
\sigma_n=\frac{\varphi^{n+2}-\psi^{n+2}}{\sqrt5}
=\frac{\varphi^{n+2}}{\sqrt5}\left(1-\left(\frac\psi\varphi\right)^{n+2}\right).
$$
Since $|\psi|<\varphi$, taking $n$th roots gives \b[$\lim_{n\to\infty}\sigma_n^{1/n}=\varphi$]. This use of the golden-ratio symbol is independent of the connection rate in Question 1.
Back to article page
