North-east-west self-avoiding walk count
= North-east-west self-avoiding walk count
{title2=$a_n=\frac{(1+\sqrt2)^{n+1}+(1-\sqrt2)^{n+1}}2$}
A horizontal run has <generating function> $R(z)=(1+z)/(1-z)$. Decomposing each walk into $H(NH)^k$ gives $A(z)=R(z)/(1-zR(z))=(1+z)/(1-2z-z^2)$. Thus $a_0=1,a_1=3$ and $a_n=2a_{n-1}+a_{n-2}$. The exponential growth rate is $1+\sqrt2$, furnishing a strict lower bound greater than two for the <connective constant> of all square-lattice <self-avoiding walks>.