CMO 1979 Problem 5

A walk consists of a sequence of steps of length 1 taken in the directions north, south, east, or west. A walk is self-avoiding if it never passes through the same point twice. Let $f(n)$ be 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 < f(n) \le 4 \cdot 3^{n - 1}.$$