Usted puede reescribir esto como:
$$\frac{m}{\sqrt{2}}-1<n<\frac{m+1}{\sqrt{2}}$$
Desde $\sqrt{2}$ es irracional, sabemos que $\frac{m}{\sqrt{2}}-1$ no es un número entero, así que para un entero $n>\frac{m}{\sqrt{2}}-1$ fib $n\geq \left\lceil \frac{m}{\sqrt{2}}-1\right\rceil =\left\lfloor \frac{m}{\sqrt{2}}\right\rfloor$.
Del mismo modo, $n<\frac{m+1}{\sqrt{2}}$ fib $n\leq \left\lfloor \frac{m+1}{\sqrt{2}}\right\rfloor$. Así que en total, estamos en busca de $m,n$ tal que $$\left\lfloor\frac{m}{\sqrt 2}\right\rfloor\leq n\leq \left\lfloor\frac{m+1}{\sqrt{2}}\right\rfloor$$
Para un determinado $m$, entonces, el número de posibles $n$: $\left\lfloor\frac{m+1}{\sqrt{2}}\right\rfloor-\left\lfloor\frac{m}{\sqrt 2}\right\rfloor +1$.
Sumando sobre todos los $m$, el resultado es $$-1+\sum_{m=1}^{1000}\left(\left\lfloor\frac{m+1}{\sqrt{2}}\right\rfloor-\left\lfloor\frac{m}{\sqrt 2}\right\rfloor +1\right)$$
(El $-1$ es porque no queremos recuento $n=0$ al $m=1$.)
Pero esto es sólo $999$, además de una suma telescópica, y vemos que el resultado es:
$$999+\left\lfloor\frac{1001}{\sqrt{2}}\right\rfloor$$
En realidad, aún más específicamente, es la siguiente:
$$1000-\lfloor\sqrt{2}\rfloor + \left\lfloor\frac{1000+1}{\sqrt{2}}\right\rfloor$$
Esto funciona para cualquier número irracional $\alpha>1$ y cualquier límite superior, $M>\alpha$, lo que da un total de: $$M-\lfloor\alpha\rfloor + \left\lfloor\frac{M+1}{\alpha}\right\rfloor$$
que cuenta con los pares de $(m,n)$ $1\leq m,n\leq M$ y
$$\frac{m}{n+1}<\alpha<\frac{m+1}n$$
