Possible positions of the knight after moving $n$ steps in Chessboard. Problem
There is a knight on an infinite chessboard. After moving one step, there are $8$ possible positions, and after moving two steps, there are $33$ possible positions. The possible position after moving n steps is $a_n$, find the formula for $a_n$.

I found this sequence is http://oeis.org/A118312
But I can't understand this Recurrence Relation
$$a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3}, \quad\quad n\geq3$$
Can someone give the intuition for this relationship?

Mordechai Katzman demonstrates in section $3$ of his paper Counting monomials (pages $5$ - $8$) that
$$a_n = \begin{cases}
          1 \quad \quad \quad \quad \quad \; \, n = 0 \\
          8 \quad \quad \quad \quad \quad \; \, n = 1 \\ 
         33 \quad \quad \quad \quad \quad n = 2 \\
1 + 4n + 7n^2 \quad \; \, n \ge 3
     \end{cases}$$
We can now prove by induction that
$$a_n = 3a_{n-1} - 3a_{n-2} + a_{n-3} = 1 + 4n + 7n^2, \quad\quad n\geq3 \tag{1}$$
To test whether $(1)$ holds for $n \ge 3$, we need to define
$$a_0 = 1 + 4(0) + 7(0)^2 = 1$$
$$a_1 = 1 + 4(1) + 7(1)^2 = 12$$
$$a_2 = 1 + 4(2) + 7(2)^2 = 37$$
For the base cases, we have
$$a_3 = 3a_2 - 3a_1 + a_0 = 3\cdot37 - 3\cdot12 + 1 = 1 + 4(3) + 7(3)^2 = 76$$
$$a_4 = 3a_3 - 3a_2 + a_1 = 3\cdot76 - 3\cdot37 + 12 = 1 + 4(4) + 7(4)^2 = 129$$
$$a_5 = 3a_4 - 3a_3 + a_2 = 3\cdot129 -3\cdot76 + 37 = 1 + 4(5) + 7(5)^2 =196$$
Now, we must prove using $(1)$ that $$a_{n+1} = 3a_n - 3a_{n-1} + a_{n-2} = 1 + 4(n+1) + 7(n+1)^2 = 7n^2 + 18n + 12$$
Substituting for $a_n, a_{n-1}$ and $a_{n-2}$, we get
\begin{align}
a_{n+1} &= 3\left(1 + 4n + 7n^2\right) -3\left(1 + 4(n-1) + 7(n-1)^2\right) + \left(1 + 4(n-2) + 7(n-2)^2\right)\\
& = 7n^2 + 18n + 12
\end{align}
$\blacksquare$
