RO-TST 1989 Problem 5

A laticial cycle of length $n$ is a sequence of lattice points $(x_k, y_k)$ , $k = 0, 1,\cdots, n$ , such that $(x_0, y_0) = (x_n, y_n) = (0, 0)$ and $|x_{k+1} -x_{k}|+|y_{k+1} - y_{k}| = 1$ for each $k$ . Prove that for all $n$ , the number of latticial cycles of length $n$ is a perfect square.