Consider a 2-dimensional random walk. The starting state is (0,0)(0,0)(0,0). In general, if the current state is (i,j)(i,j)(i,j), it can move to state (i+1,j+1)(i+1,j+1)(i+1,j+1), (i+1,j−1)(i+1,j-1)(i+1,j−1), (i−1,j+1)(i-1,j+1)(i−1,j+1), (i−1,j−1)(i-1,j-1)(i−1,j−1), or (i,j)(i,j)(i,j). What is the number of possible states after nnn steps?
