Question 8
A walk consists of a sequence of steps of length $1$ taken in directions north, south, east or west. A walk is self-avoiding if it never passes through the same point twice. Let $f(n)$ denote the number of $n$-step self-avoiding walks which begin at the origin. Compute $f(1)$, $f(2)$, $f(3)$, $f(4)$, and show that
$$
2^{n} \lt f(n) \leq 4 \cdot 3^{n-1}
$$
$$
2^{n} \lt f(n) \leq 4 \cdot 3^{n-1}
$$