对 $m = 1, 2$, 取几组合法 $(i, j)$ 即证.
对 $m \geqslant 3$, 设 $f_m$ 表示 $a_{1 \sim 4m + 2}$ 中能取出的合法数对数量.
注意到 $a_{1 \sim 4m + 2}$ 中任意长度为 $4l + 2$ 的子区间对应的答案均为 $f_l$, 则取分界点 $p_1 = 4, p_2 = 4m - 2$ 进行容斥.
$$\begin{aligned}
f_m &= f_m[i \not\in [1, p_1]~\textrm{or}~j \not\in [p_2 + 1, 4m + 2]] + f_m[i \in [1, p_1]~\textrm{and}~j \in [p_2 + 1, 4m + 2]]\\
&= f_m[i, j \in [p_1 + 1, 4m + 2]] + f_m[i, j \in [1, p_2]] - f_m[i, j \in [p_1 + 1, p_2]] \\&~~~~+ f_m[i \in [1, p_1]~\textrm{and}~j \in [p_2 + 1, 4m + 2]]\\
&= 2f_{m - 1} - f_{m - 2} + f_m[i \in [1, p_1]~\textrm{and}~j \in [p_2 + 1, 4m + 2]]
\end{aligned}
$$
考虑求 $f_m[i \in [1, p_1]~\textrm{and}~j \in [p_2 + 1, 4m + 2]]$ 的下界.
- 显然 $(i, j) = (1, 4m + 2)$ 是合法的.
- 对于 $(i, j) = (2, 4m + 1)$, 当 $m = 3$ 时其合法性在第 $(2)$ 问中已证. 当 $m > 3$ 时, 从前后各取 $2$ 个下标公差为 $2$ 的子序列, 注意到只看子区间 $[9, 4m - 6]$, 其中 $10$ 和 $4m - 7$ 已经被取过了, 于是变成了等价的子问题. 故归纳可证 $(i, j) = (2, 4m + 1)$ 是合法的.
此时有 $f_m[i \in [1, p_1]~\textrm{and}~j \in [p_2 + 1, 4m + 2]] \geqslant 2$, 于是 $f_m \geqslant 2f_{m - 1} - f_{m - 2} + 2$.
取 $f'_m = 2f'_{m - 1} - f'_{m - 2} + 2 \leqslant f_m, f'_1 = 3, f'_2 = 7$.
变换得 $(f'_m - f'_{m - 1}) = (f'_{m - 1} - f'_{m - 2}) + 2$, 由熟知的方法解得 $f_m \geqslant f'_m = m ^ 2 + m + 1$.
于是 $P_m = \frac{f_m}{\binom{4m + 2}{2}} \geqslant \frac{f'_m}{\binom{4m + 2}{2}} = \frac{m ^ 2 + m + 1}{8m^2 + 6m + 1} > \frac{1}{8}$, 原命题得证.