8
$\begingroup$

Prove that the inequality $$\left|\frac{m}{n}-\frac{1+\sqrt{5}}{2}\right|<\frac{1}{mn}$$ holds for positive integers $m, n$ if and only if $m$ and $n$ where $m > n$ are two successive terms of the Fibonacci sequence.

I thought about using the explicit formula for the Fibonacci sequence, which is $$F_n = \dfrac{1}{\sqrt{5}}\left(\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right),$$ but this seems to get computational. Is there an easier way to think about this?

$\endgroup$
  • $\begingroup$ Wow, the most interesting part about this to me is that even Fibonacci-like sequences don't satisfy this inequality (i.e, adding successive terms of the sequence with starting conditions other than 1 and 1). $\endgroup$ – Nitin Dec 14 '16 at 4:22
  • 1
    $\begingroup$ You probably want to look at the continued fraction expansion of the golden ratio. $\endgroup$ – ajs3 Dec 14 '16 at 4:27
  • $\begingroup$ you may want to check out Hurwitz's theorem en.wikipedia.org/wiki/Hurwitz%27s_theorem_(number_theory) $\endgroup$ – Anurag A Dec 14 '16 at 4:33
7
$\begingroup$

$\varphi = \frac{1+\sqrt{5}}{2}$ is the root of $x^2-x-1=0$. In fact $x^2-x-1=\left(x - \frac{1+\sqrt{5}}{2}\right) \cdot \left(x - \frac{1-\sqrt{5}}{2}\right)$. Taking $x=\frac{F_{n+1}}{F_n}$, we have:

$$\left|\left(\frac{F_{n+1}}{F_n}\right)^2-\frac{F_{n+1}}{F_n}-1\right|=\left|\frac{F_{n+1}}{F_n} - \frac{1+\sqrt{5}}{2}\right| \cdot \left|\frac{F_{n+1}}{F_n} - \frac{1-\sqrt{5}}{2}\right| \Leftrightarrow $$ $$\left|\frac{F_{n+1}^2-F_{n+1}F_n-F_n^2}{F_n^2}\right|=\left|\frac{F_{n+1}}{F_n} - \frac{1+\sqrt{5}}{2}\right| \cdot \left|\frac{F_{n+1}}{F_n} + \frac{\sqrt{5}-1}{2}\right| \Leftrightarrow $$ Using Will's hint (a particular case of this): $$\frac{1}{F_n^2}=\left|\frac{F_{n+1}}{F_n} - \frac{1+\sqrt{5}}{2}\right| \cdot \left(\frac{F_{n+1}}{F_n} + \frac{\sqrt{5}-1}{2}\right) \Rightarrow$$ $$\frac{1}{F_n^2}>\left|\frac{F_{n+1}}{F_n} - \frac{1+\sqrt{5}}{2}\right| \cdot \frac{F_{n+1}}{F_n}$$ or $$\left|\frac{F_{n+1}}{F_n} - \frac{1+\sqrt{5}}{2}\right| < \frac{1}{F_n \cdot F_{n+1}}$$

Now, let's assume $\left|\frac{m}{n} - \frac{1+\sqrt{5}}{2}\right| < \frac{1}{mn}, m>n$ then, using the same polynomial: $$\left|\left(\frac{m}{n}\right)^2-\frac{m}{n}-1\right|=\left|\frac{m}{n} - \frac{1+\sqrt{5}}{2}\right| \cdot \left|\frac{m}{n} - \frac{1-\sqrt{5}}{2}\right| < $$ $$\frac{1}{mn}\cdot \left(\frac{m}{n} + \frac{\sqrt{5}-1}{2}\right)$$ or $$\left|m^2-mn-n^2\right|< \frac{n}{m} \cdot \left(\frac{m}{n} + \frac{\sqrt{5}-1}{2}\right)<\frac{n}{m} \cdot \left(\frac{m}{n} + 1\right)<2$$ which means $\left|m^2-mn-n^2\right|=0$ or $\left|m^2-mn-n^2\right|=1$. The first one, being related to $x^2-x-1=0$, has no integer solutions other than $m=n=0$ which is not $m>n$. Fibonacci numbers satisfy the latter.

Are Fibonacci the only numbers satisfying $\left|m^2-mn-n^2\right|=1$? Well, $1$ and $0$ do and if we assume $m=n+q$ we have:

$$|m^2-mn-n^2|=|(n+q)^2 - (n+q)n - n^2|=|n^2+2nq+q^2 - n^2 - nq - n^2|=$$ $$|q^2+nq-n^2|=|n^2-nq-q^2|=1$$ clearly $n>q>0$, otherwise $q^2+nq-n^2 \geq n^2 + n^2 - n^2\geq 1$ (equality in fact is possible only for $n=q=1$). Next we take $n=q+q_1$ and so on, leading to $m>n>q>q_1>...>q_p > 0$, i.e. it's a finite process. $q_p=1$ otherwise it can be "split" further (e.g. $q_p=2$ leads to $q_{p+1}=1$ and $|2^2-2\cdot 1 -1^1|=1$). Eventually, this leads to Fibonacci numbers only.

$\endgroup$
  • 1
    $\begingroup$ Very nice and complete. I've understood first time a proof of that type.Thanks! (+1) $\endgroup$ – Gottfried Helms Dec 4 '17 at 10:16
5
$\begingroup$

If $m > n$ are consecutive Fibonacci numbers, $$ m^2 - mn - n^2 = \pm 1 $$

The quadratic form $m^2 - mn - n^2$ factors nicely when we add $\frac{1 + \sqrt 5}{2}$ and $\frac{1 - \sqrt 5}{2}$ to the integers

$\endgroup$
  • 2
    $\begingroup$ How does this solve the question? $\endgroup$ – user19405892 Dec 14 '16 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.