Possible positions of the knight after moving $n$ steps in Chessboard.

Question

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?

Answer 1

An intuitive setup

The growth of the number of knight moves for $n \ge 3$ can be modelled by an octagon increasing linearly in size, simulated below

Simulation taken from here.

We will use the following image to construct the recurrence relation.

In the image above, $$a_n = \text{black points + red points + green points + blue points}$$ $$a_{n-1} - a_{n-2} = (\text{black points + red points + green points}) - (\text{black points + red points}) = \text{green points}$$ $$a_{n-3} = \text{black points}$$

Hence, the relation is equivalent to proving $$3\cdot\text{green points} + \text{black points} = \text{black points + red points + green points + blue points}$$ $$\iff 2\cdot\text{green points} = \text{red points + blue points}$$

As the growth of the number of points is linear, we have $$a = \text{red points}$$ $$a + d = \text{green points}$$ $$a + 2d = \text{blue points}$$

It holds that $$2(a + d) = a + (a + 2d)$$

$\blacksquare$

Answer 2

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$