2

I'm trying to better understand the Fibonacci recurrence. I understand that the closed form solution is: $$F_n=\frac{1}{\sqrt{5}}\bigg[\Big(\frac{1+\sqrt5}{2}\Big)^n-\Big(\frac{1-\sqrt5}{2}\Big)^n\bigg].$$

I read that is can simplified as. $$F_n=\operatorname{round} (\phi^n/\sqrt{5}),$$

where $\phi=(1+\sqrt{5})/2$.

I'm confused as how this simplifies to this.

Rócherz
  • 3,976
Camilo
  • 21
  • 1
  • 2
    The second term decays to zero exponentially quickly, because $(1 - \sqrt{5}) / 2 \approx -0.6.$ –  May 06 '18 at 22:13

1 Answers1

2

Let $\displaystyle a_n=\frac{1}{\sqrt{5}}\Big(\frac{1+\sqrt5}{2}\Big)^n $ and $\displaystyle b_n=\frac{1}{\sqrt{5}}\Big(\frac{1-\sqrt5}{2}\Big)^n $. Then $F_n = a_n - b_n$.

Then $b_n$ is an alternating sequence that converges to $0$: $$ -0.5 < b_1 < b_3 < b_5 < \cdots < 0 < \cdots < b_4 < b_2 < b_0 < 0.5 $$

For the task at hand, the key point is just that $-0.5 < b_n < 0.5$.

To prove that $F_n=\text{round} (a_n)=\text{floor} (a_n+0.5)$, we have to prove that $$ F_n \le a_n + 0.5 < F_n + 1 $$ Indeed, $$ F_n = a_n - b_n < a_n + 0.5 $$ and $$ F_n + 1 = a_n - b_n + 1 > a_n - 0.5 + 1 = a_n + 0.5 $$

lhf
  • 216,483