= Solution
Split a <self-avoiding walk> of length $m+n$ after its first $m$ steps. Its prefix is one of the $c_m$ walks, and its translated suffix is a <self-avoiding walk> of length $n$ from the origin. The pair determines the original walk, although not every pair can be concatenated without intersection. Therefore
$$
c_{m+n}\le c_mc_n.
$$
All $c_n$ are positive, so $x_n=\log c_n$ is a <subadditive sequence>. The <Fekete lemma> gives existence of $\lim_n n^{-1}\log c_n$ and consequently of the <connective constant>.
For a lower bound, all words of length $n$ using only north and east steps produce distinct <self-avoiding walks>: the sum of the two coordinates increases at each step. Thus $c_n\ge2^n$. For an upper bound, there are four choices for the first step and at most three thereafter, since a <self-avoiding walk> cannot immediately reverse its previous <edge>. Hence $c_n\le4\,3^{n-1}$. Taking $n$th roots proves
$$
\boxed{\kappa=\lim_{n\to\infty}c_n^{1/n}
=\inf_{n\ge1}c_n^{1/n},\qquad 2\le\kappa\le3.}
$$
The elementary upper bound counts all non-backtracking walks, including some that self-intersect, so it is an upper estimate rather than an equality.
Back to article page
