Show that $b\ge f_{n+1}$.

Remark: $\frac{f_{r+1}}{f_{r}}$ are convergents of the continued fraction of $\varphi$ the golden ratio. There is a theorem that any convergent is nearer to the number (whose CF we are looking at) than any other rational with a smaller denominator. That or something similar can potentially be used here.

---

Anyway, here is a simple proof that $b \ge f_{n+1}$

First we show that $b \gt f_n$.

Subtract $\frac{f_n}{f_{n-1}}$ from the given inequality to get

$$0 \lt \frac{a}{b} - \frac{f_n}{f_{n-1}} \lt \frac{f_{n+1}}{f_n} - \frac{f_n}{f_{n-1}} = \frac{1}{f_nf_{n-1}}$$

We used the identity $|f_{n+1}f_{n-1} - f_n^2| = 1$ (Cassini's formula) to simplify the right hand side.

i.e

$$ 0 \lt \frac{af_{n-1} - bf_n}{b} \lt \frac{1}{f_{n}}$$

And so

$$ b \gt f_n(af_{n-1} - bf_n)$$

Now $af_{n-1} - bf_n$ is a positive integer and so is $\ge 1$ and so $b \gt f_{n}$

Now we show that $b \ge f_{n+1}$.

Now if $af_{n-1} - bf_n \ge 2$, then we will have $b \gt 2 f_n \gt f_n + f_{n-1} = f_{n+1}$.

So assume that $$af_{n-1} - b f_n = 1$$

Now all solutions of $$au + bv = 1$$ are given by

$$a_t = a_0 + tv$$ $$b_t = b_0 - tu$$

where $t$ is an integer param, and $a_0, b_0$ are some initial solution.

For us (again using Cassini's) $$a_0 = f_{n+1}$$ $$b_0 = f_n$$ $$u = f_{n-1}$$ $$v = -f_n$$

Thus the solutions are $$a_t = f_{n+1} - tf_n$$ $$ b_t = f_n - t f_{n-1}$$

Since we want $$b_t \gt f_n$$ we need $t \lt 0$ in which case $$b = b_t \ge f_n + f_{n-1} = f_{n+1}$$

Suppose $a,a',a''$ are non-negative integers and $b,b',b''$ are positive integers with $a''b'-b''a'=1$ and $\frac {a'}{b'}<\frac {a}{b}<\frac {a''}{b''}.$ Then $$0<ab'-a'b \quad \text { and }\quad 0<a''b-ab''.$$ Since these are all integers we have $$1\leq ab'-a'b \quad \text { and }\quad 1\leq a''b-ab''.$$ Multiplying the left inequality above by $b'',$ and multiplying the right inequality above by $b'$ we have $$b''\leq b''ab'-b''a'b \quad \text { and }\quad b'\leq b'a''b-b'a'b''.$$ Adding the above two inequalities we have $$b''+b'\leq (b''ab'-b''a'b)+(b'a''b-b'ab'')=b(a''b'-b''a')=b.$$

Since $f_n^2-f_{n-1}f_{n+1}=(-1)^{n-1},$ if $(a',b')=(f_n,f_{n-1})$ and $(a'',b'')=(f_{n+1},f_n)$ and if $\frac {a''}{b''}>\frac {a'}{b'}$, then $a''b'-b''a'=1.$