Show that $b\ge f_{n+1}$. The Fibonacci sequence is defined as $f_1=f_2=1, f_{n+2}=f_{n+1}+f_{n}$. Assume that ${f_n \over f_{n-1}} \lt {a \over b} \lt {f_{n+1} \over f_n}$ ($a$ and $b$ are positive integers with no common prime factors). Show that $b\ge f_{n+1}$.
 A: 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}$$
A: 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.$
