Irish Mathematical Olympiad

We let $E_n$ be the number of nice isosceles triangles for which the coordinates $(x, y)$ of all vertices satisfy $y \le n$ and for at least one vertex we have $y = n$. These triangles are part of the count for $V_n$ but not for $V_{n-1}$. Therefore, we obtain
$$V_n = V_{n-1} + E_n \quad \text{for } n \ge 1. \quad (19)$$
We remark that $E_n$ is also equal to the number of nice isosceles triangles for which the coordinates $(x, y)$ of all vertices satisfy $y \le n$ and for at least one vertex we have $y = 0$. To see this, replace each vertex $(x, y)$ by $(x, n-y)$. Let now $B_n$ denote the number of all nice isosceles triangles for which the coordinates $(x, y)$ of all vertices satisfy $y \le n$ and at least one vertex has $y = n$ and at least one vertex has $y = 0$. We then have
$$E_n = E_{n-1} + B_n \quad \text{for } n \ge 2, \quad (20)$$
because we can split the set of nice isosceles triangles for which the coordinates $(x, y)$ of all vertices satisfy $y \le n$ and for at least one vertex we have $y = 0$ (totalling to $E_n$) into the set of those for which all vertices have $y < n$ (giving $E_{n-1}$) and those for which at least one vertex has $y = n$ (giving $B_n$).

We now split the set (with $B_n$ elements) of all nice isosceles triangles for which the coordinates $(x, y)$ of all vertices satisfy $y \le n$ and at least one vertex has $y = n$ and at least one vertex has $y = 0$ into two subsets. One subset contains all those triangles that have a vertex with coordinates $(x, y)$ with $0 < y < n$. The number of triangles in this subset is denoted by $C_n$. The other subset consists of those triangles that do not have a vertex with $0 < y < n$ and its number of elements is denoted by $D_n$. We then have $B_n = C_n + D_n$.

The crucial observations are that $D_n$ does not depend on $n$ and that $C_n$ depends on the parity of $n$ only, provided that $n$ is large enough. We now explain why.

Consider a nice isosceles triangle that has vertices $P = (a, 0)$, $Q = (b, n)$ and $R = (c, n)$. Both, $|PQ|$ and $|PR|$, are at least $n$ and $|QR| = |b - c| \le 2018$. If $n > 2018$, we cannot have an isosceles triangle in which $QR$ is one of the equal sides. Hence, we need to have $|PQ| = |PR|$ and this happens exactly when $2a = b + c$. Therefore, $P$ is completely determined by $Q$ and $R$ and no such $P$ exists if $a$ and $b$ differ by an odd number. This shows that $D_n$ does not depend on $n$ as long as $n > 2018$.

Consider now a nice isosceles triangle $PQR$ with vertices $P = (a, 0)$, $Q = (b, n)$ and $R = (c, y)$ such that $0 < y < n$. Considering the diagonal from $(0, 0)$ to $(2018, n - 1)$ we see that $|PR|^2$ and $|QR|^2$ do not exceed $2018^2 + (n - 1)^2$. Because we also have $|PQ|^2 \ge n^2$, we obtain $|PQ| > |QR|$ and $|PQ| > |PR|$ as soon as $2n > 2018^2 + 1$. Therefore, for such $n$, we need to have $|PR| = |QR|$. If we let $r = |a - c|$ and $s = |b - c|$, we get
$$r^2 + y^2 = |PR|^2 = |QR|^2 = s^2 + (n - y)^2,$$
i.e. $r^2 - s^2 = n(n - 2y)$. If $r \neq s$, then $n \neq 2y$ and $|n - 2y| \ge 1$, hence $|r^2 - s^2| \ge n$. In case $n = 2018^2$ and $n \neq 2y$, we even have $|n - 2y| \ge 2$ and we obtain $|r^2 - s^2| \ge 2 \cdot 2018^2 > 2018^2$. However, we have $0 \le r, s \le 2018$ and so $|r^2 - s^2| \le 2018^2$.

This shows that we need to have $r = s$ and $n = 2y$, whenever $n \ge 2018^2$. In particular, if $n \ge 2018^2$ is odd, $C_n = 0$. If $n \ge 2018^2$ is even, $C_n$ is not equal to zero but does not depend on $n$ because the triangles we count are determined by the choice of $a = b$ and $c \neq a$. Therefore, if $n \ge 2018^2$, $C_n$ depends on the parity of $n$ only.

Because $B_n = C_n + D_n$, we see now that $B_n$ depends on the parity of $n$ only, i.e.
$$B_{n+2} = B_n \text{ for } n \ge 2018^2. \qquad (21)$$

The desired recurrence is now obtained as follows:
$$\begin{align*} V_{n+1} &= V_n + E_{n+1} \\ &= V_n + E_n + B_{n+1} \\ &= V_n + V_n - V_{n-1} + B_{n+1} \\ &= 2V_n - V_{n-1} + B_{n+1} \end{align*}$$
using (19)
valid for all $n \ge 1$.

Replacing $n$ by $n-2$ we obtain
$$V_n = 2V_{n-1} - V_{n-2} + B_n \quad \text{for all } n \ge 3.$$
Substituting this in the previous equation finally gives
$$\begin{align*} V_{n+1} &= 2V_n - 2V_{n-2} + V_{n-3} - B_{n-1} + B_{n+1} \\ &= 2V_n - 2V_{n-2} + V_{n-3} \end{align*}$$
using (21)
for all $n > 2018^2$.