Number of walks of length $n$ on $\mathbb{Z}$ times a square

Question

Let $a_n$ denote the number of self-avoiding walks of length $n \in \mathbb{N}$ on $\mathbb{Z}$ times a square, that is $4$ parallel copies of $\mathbb{Z}$ that are sideways connected in parallel squares. I want to compute $a_4$ and show that $$2^n \leq a_{2n} \leq 4 \cdot 3^{2n}. $$ I am looking for a rigorous way of doing this instead of an intuitive explanation.

Answer 1

I think you forgot to specify that the walks all start at some origin; otherwise there are countably infinitely many of them.

To find $2^n$ different self-avoiding walks of length $2n$, alternate going along the (say, positive) $\mathbb Z$ direction and taking either a clockwise or a counterclockwise step along the square.

Since every vertex has $4$ neighbours, $4\cdot3^{2n-1}$ is the number of walks of length $2n$ that don't immediately return to the same place, and thus an upper bound for the number $a_{2n}$ of self-avoiding walks.

As for $a_4$, it shouldn't be too difficult to count by hand.