Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 30 / 1 / b

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. ThereforeAll $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\ge 2^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\le 43^{n-1}$. Taking $n$th roots provesThe elementary upper bound counts all non-backtracking walks, including some that self-intersect, so it is an upper estimate rather than an equality.