Consider the Fibonacci sequence {Fi}i≥1\{ F_i \}_{i \ge 1}:

1,1,2,3,5,8,13,21,.... 1, 1, 2, 3, 5, 8, 13, 21, ....

which is defined recursively as follows:

{F1=1F2=1Fn+2=Fn+1+Fnn≥1 \begin{cases} F_1 = 1 \\ F_2 = 1 \\ F_{n + 2} = F_{n + 1} + F_{n} \quad n \ge 1 \end{cases}

We discuss some techniques for computing the (approximate) closed form formula for FnF_n for n≥1n \ge 1.

Method 1

We guess that FnF_n is of closed form as Fn=znF_n = z^n for some z∈Rz \in \R. As Fn+2=Fn+1+FnF_{n + 2} = F_{n + 1} + F_n, zz needs to satisfies

z2=z+1 z^2 = z + 1

The quadratic equation has two roots, z1=1+52z_1 = \frac{1 + \sqrt 5}{2} and z1=1−52z_1 = \frac{1 - \sqrt 5}{2} respectively.

Let a,b∈Ra, b \in \R. Fn=az1n+bz2nF_n = a z_1^n + b z_2^n is also a possible solution that satisfies Fn+2=Fn+1+FnF_{n + 2} = F_{n + 1} + F_n. We can compute the exact value of aa and bb by the constraints F1=F2=1F_1 = F_2 = 1:

az1+bz2=1az12+bz22=1 a z_1 + b z_2 = 1 \\ a z_1^2 + b z_2^2 = 1

i.e.,

a(1+5)+b(1−5)=2a(6+25)+b(6−25)=4 a (1 + \sqrt 5) + b (1 - \sqrt 5) = 2 \\ a (6 + 2\sqrt 5) + b (6 - 2 \sqrt 5) = 4

Therefore a=1/5a = 1 / \sqrt 5, b=−1/5b = -1 / \sqrt 5, and

Fn=(1+52)n−(1−52)n5 F_n = \frac{ (\frac{1 + \sqrt 5} {2})^n - (\frac{1 - \sqrt 5} {2})^n }{\sqrt 5}

■\blacksquare

Method 2

Consider the intervals derived from the sequences:

1,1,2,3,5,8,13,21,.... 1, 1, 2, 3, 5, 8, 13, 21, .... →[11,21],[32,53],[85,138],[2113,3421],... \rightarrow [\frac{1}{1}, \frac{2}{1} ], \quad [ \frac{3}{2} , \frac{5}{3} ], \quad [ \frac{8}{5} , \frac{13}{8} ], \quad [ \frac{21}{13}, \frac{34}{21} ], ...

Define xn=Fn+1Fnx_n = \frac{F_{n + 1} }{F_n} and denote InI_n the nn-th interval. Then

In=[x2n−1,x2n] I_n = [x_{2n - 1}, x_{2n } ]

By observation of the first few InI_n's, they seems to be nested closed intervals, with shrinking lengths. If the length of InI_n converges to 00, then the limit of xnx_n exists. Suppose that

lim⁡nxn=ϕ \lim_{n} x_n = \phi

Then

lim⁡nFn=O(ϕn) \lim_n F_n = O(\phi^n )

We will prove this in what follows.

The key transformation we performed is

xn=Fn+1Fn=Fn+Fn−1Fn=1+1xn−1. x_{n} = \frac{ F_{n + 1} }{F_{n} } = \frac{ F_{n } + F_{n - 1 } }{ F_{n} } = 1 + \frac{1}{ x_{ n - 1} }.
Lemma 1
x1<x3<x5<x7<...x2>x4>x6>x8>... x_1 < x_3 < x_5 < x_7 < ... \\ x_2 > x_4 > x_6 > x_8 > ... \\

Proof: For n≥1n \ge 1,

x2n+2−x2n=1x2n+1−1x2n−1=x2n−1−x2n+1x2n+1x2n−1. x_{2n + 2} - x_{2n} = \frac{1}{ x_{2n + 1} } - \frac{1}{ x_{2n - 1} } = \frac{ x_{2n - 1} - x_{2n + 1} }{ x_{2n + 1} x_{2n - 1} }.

Similarly,

x2n+1−x2n−1=1x2n−1x2n−2=x2n−2−x2nx2nx2n−2. x_{2n + 1} - x_{2n - 1} = \frac{1}{ x_{2n} } - \frac{1}{ x_{2n - 2} } = \frac{ x_{2n - 2} - x_{2n} }{ x_{2n} x_{2n - 2} }.

As x3−x1=3/2−1>0x_3 - x_1 = 3 /2 - 1 > 0, and x4−x2=5/3−2<0x_4 - x_2 = 5 / 3 - 2 < 0, the lemma follows from induction.

□\square

Lemma 2. For n≥1n \ge 1,
x2n−x2n−1≥0 x_{2n} - x_{2n - 1} \ge 0

Proof: Clearly this holds for n=1n = 1. Consider n≥2n \ge 2,

x2n−x2n−1=1x2n−1−1x2n−2=−x2n−1−x2n−2x2n−1⋅x2n−2=x2n−2−x2n−3x2n−1⋅x2n−2⋅x2n−2⋅x2n−3 x_{2n} - x_{2n - 1} = \frac{1}{x_{2n - 1} } - \frac{1}{x_{2n - 2} } = - \frac{ x_{2n - 1} - x_{2n - 2} }{x_{2n - 1} \cdot x_{2n - 2}} = \frac{ x_{2n - 2} - x_{2n - 3} }{x_{2n - 1} \cdot x_{2n - 2} \cdot x_{2n - 2} \cdot x_{2n - 3} }

The claim follows from induction.

Corollary 2. For n≥2n \ge 2,
In=x2n−x2n−1=x2n−2−x2n−3x2n−1⋅x2n−2⋅x2n−2⋅x2n−3≤x2n−2−x2n−3x2n−1≤x2n−2−x2n−3x3=23(x2n−2−x2n−3)=23In−1 \begin{aligned} I_n &= x_{2n} - x_{2n - 1} \\ &= \frac{ x_{2n - 2} - x_{2n - 3} }{x_{2n - 1} \cdot x_{2n - 2} \cdot x_{2n - 2} \cdot x_{2n - 3} } \\ &\le \frac{ x_{2n - 2} - x_{2n - 3} }{ x_{2n - 1} } \\ &\le \frac{ x_{2n - 2} - x_{2n - 3} }{ x_3 } \\ &= \frac{2}{3} (x_{2n - 2} - x_{2n - 3}) \\ &= \frac{2}{3} I_{n - 1} \end{aligned}

Hence lim⁡n∣In∣=0\lim_n |I_n| = 0.

□\square

Combining lemma 1 and 2, we conclude that lim⁡xn=ϕ\lim x_n = \phi exists. As

lim⁡xn=ϕ=lim⁡(1+1xn−1)=1+1ϕ \lim x_n = \phi = \lim (1 + \frac{1}{x_{n - 1} } ) = 1 + \frac{1}{\phi }

We conclude that ϕ=1+52\phi = \frac{ 1 + \sqrt{5} }{2 }.