North-east-west self-avoiding walk count ($a_n=\frac{(1+\sqrt{2}{)}^{n+1}+(1-\sqrt{2}{)}^{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+\sqrt{2}$, furnishing a strict lower bound greater than two for the connective constant of all square-lattice self-avoiding walks.