# 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?

## 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$$

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$$

• It seems like the heavy lift here is coming up with the value of $a_n$ in the first place. Once you have it, you can show it satisfies the recurrence. Do you have any insights into where $a_n$ comes from? May 19, 2022 at 16:16
• @templatetypedef See my new answer.
– user905694
May 19, 2022 at 17:28
• @templatetypedef In the context of this answer, $a_n$ comes from the paper I cited.
– user905694
May 19, 2022 at 17:34