, 2009

For each $n \in \mathbb{N}^*$, denote by $d_n$ the number to be found.
Consider the table of size $2 \times n$. Write in each square of the table in the order from left to right and from top to bottom the numbers from $1$ to $2n$. (See Pic. 1).
Call the $n$-th square of the first row and the first square of the second row special squares.
Then two numbers $a, b \in T$ satisfy $|a - b| \in \{1; n\}$ iff they lie in two squares with common side or if they lie in the special squares.

Hence, $d_n$ is the number of the ways of choosing some squares of the table (including the choice of $0$ squares) with the property that in each choice there are no squares with common side and the two special squares are not chosen together.
For each $n \in \mathbb{N}^*$, denote:
+ $k_n$ the number of choices of squares in which there are no squares with common sides; (*)
+ $s_n$ the number of choices of squares in which there are no squares with common sides and the two special squares are chosen.
Thus: $d_n = k_n - s_n$.

* Compute $k_n$.
The set of choices satisfying (*) consists of:
+ $k_{n-1}$ choices, in each of which the square of the first column is not chosen;
+ $2t_{n-1}$ choices, in each of which a square of the first column is chosen;
where $t_n$ is the number of choices satisfying (*) from the table $2 \times n$ cut off one square. (See Pic. 2).

Thus $k_n = k_{n-1} + 2t_{n-1}$. (5.1)
On the other hand, choices satisfying (*) from such a table $2 \times n$ consist of:
+ $k_{n-1}$ choices, in each of which the square with mark "x" is not chosen;
+ $t_{n-1}$ choices, in each of which the square with mark "x" is chosen.
Hence: $t_n = k_{n-1} + t_{n-2}$.
Therefore, according to (5.1) we have:
$$k_n = k_{n-1} + 2(k_{n-2} + t_{n-2}) = 2k_{n-1} + k_{n-2} \quad \forall n \ge 3. \quad (5.2)$$
$$\text{Direct count gives: } k_1 = 3 \text{ and } k_2 = 7. \quad (5.3)$$
The recurrent relation (5.1) has characteristic equation: $x^2 - 2x - 1 = 0$.

$$\text{This yields: } k_n = C_1(1 + \sqrt{2})^n + C_2(1 - \sqrt{2})^n \quad \forall n \ge 1. \qquad (5.4)$$
By means of (5.3), we find: $C_1 = \frac{1+\sqrt{2}}{2}$ and $C_2 = \frac{1-\sqrt{2}}{2}$.
$$\text{Thus } k_n = \frac{(1 + \sqrt{2})^{n+1} + (1 - \sqrt{2})^{n+1}}{2}. \qquad (5.5)$$

• Compute $s_n$.
We have, $s_1 = 0$, $s_2 = s_3 = 1$ and for $n \ge 4$ we have:
$s_n = h_{n-2},$
where $h_n$ is the number of choices satisfying (*) from the table $2 \times n$ cut off two squares. (See Pic. 3).

Pic 3

Since $s_3 = 1$, let $h_1 = 1$. Direct count gives $h_2 = 4$.
Let $n \ge 3$.
The choices satisfying (*) from the table $2 \times n$ cut off two squares as above consist of:
+ $k_{n-2}$ choices, in each of which both squares $A$ and $B$ are not chosen;
+ $2t_{n-2}$ choices, in each of which exactly one of squares $A$, $B$ is chosen;
+ $h_{n-2}$ choices, in each of which both of squares $A$ and $B$ are chosen.
$$\text{Hence } h_n = k_{n-2} + 2t_{n-2} + h_{n-2} = k_{n-1} + h_{n-2}. \quad \forall n \ge 3. \quad (5.6)$$
$$(5.2) \text{ and (5.6) imply } 2h_n - k_n = 2h_{n-2} - k_{n-2} \quad \forall n \ge 3.$$
$$\text{Hence } 2h_n - k_n = (-1)^n \quad \forall n \ge 1.$$
$$\text{Consequently } s_n = h_{n-2} = \frac{k_{n-2} + (-1)^{n-2}}{2} \quad \forall n \ge 3.$$
$$\bullet \text{ Thus } d_1 = 3, d_2 = 6 \text{ and } d_n = \frac{2k_n - k_{n-2} + (-1)^{n-3}}{2} \quad \forall n \ge 3,$$
where $k_n$ is given as in (5.5).