$\frac{a+b}{2}\cdot \frac{a-b}{2}=n^2+n+1$ (Their difference is $b$) $a^2=(2n+1)^2+b^2+3$ $b^2+3\ge 2(2n+1)+1$

Write $t(t+k) = n^2+n+1$. Then, by multiplying by $4$ we can rewrite the expression as follows: $(2t+k)^2 -k^2 = (2n+1)^2 + 3$. Now, as $ 3< (2n+2)^2 - (2n+1)^2$ as $n \geq 1$ we obtain that $3+k^2 \geq (2n+2)^2 - (2n+1)^2 = 4n+3 \implies k \geq 2\sqrt{n}$ as required.