logo

Derivation of the General Term of the Fibonacci Sequence 📂Lemmas

Derivation of the General Term of the Fibonacci Sequence

Theorem

Let’s say that the sequence sequence {Fn}n=0∞\left\{ F_{n} \right\}_{n=0}^{\infty} is defined as Fn+1:=Fn+Fn−1F_{n+1} := F_{n} + F_{n-1}. If F0=F1=1F_{0} = F_{1} = 1, then for r0:=1+52\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}} and r1:=1−52\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}, Fn=r0n+1−r1n+1r0−r1 F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }}

Description

  • Note that the Fibonacci sequence introduced above starts from the 00th term.

The general term of the Fibonacci sequence is also called the Binet Formula. The Fibonacci sequence has so many properties and is applied in unexpected areas. There are even books solely about the Fibonacci sequence, and there are many explanations in textbooks and on the internet, so we will omit them here.

Derivation

Consider the equation r2−r−1=(r−1+52)(r−1−52)=(r−r0)(r−r1) \begin{align*} & r^2 - r - 1 \\ =& \left( r - {{1 + \sqrt{5} } \over {2}} \right) \left( r - {{1 - \sqrt{5} } \over {2}} \right) \\ =& ( r - r_{0} ) ( r - r_{1} ) \end{align*} According to this equation, r02−r0−1=0r12−r1−1=0 {r_{0}}^2 - {r_{0}} - 1 = 0 \\ {r_{1}}^2 - {r_{1}} - 1 = 0 is true. If we rewrite it to make it look a bit nicer, r02=r0+1r12=r1+1 {r_{0}}^2 = {r_{0}} + 1 \\ {r_{1}}^2 = {r_{1}} + 1 . Now, using mathematical induction, Fn=r0n+1−r1n+1r0−r1 F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} will be shown to be true.

When n=0n=0, F0=r00+1−r10+1r0−r1=1 F_{0} = {{ {r_{0}}^{0+1} - {r_{1}}^{0+1} } \over { r_{0} - r_{1} }} = 1

When n=1n=1, F1=r01+1−r11+1r0−r1=1 F_{1} = {{ {r_{0}}^{1+1} - {r_{1}}^{1+1} } \over { r_{0} - r_{1} }} = 1

Assuming when n=kn=k Fk=r0k+1−r1k+1r0−r1 F_{k} = {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }} is true,

{Fk}\left\{ F_{k} \right\} is the Fibonacci sequence, thus

Fk+1=Fk+Fk−1=r0k+1−r1k+1r0−r1+r0k−r1kr0−r1=r0k(r0+1)−r1k(r1+1)r0−r1=r0k⋅r02−r1k⋅r12r0−r1∵r02=r0+1,r12=r1+1=r0k+2−r1k+2r0−r1 \begin{align*} F_{k+1} =& F_{k} + F_{k-1} \\ =& {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }} + {{ {r_{0}}^{k} - {r_{1}}^{k} } \over { r_{0} - r_{1} }} \\ =& {{ {r_{0}}^{k} ( r_{0} + 1 ) - {r_{1}}^{k} ( r_{1} + 1 ) } \over { r_{0} - r_{1} }} \\ =& {{ {r_{0}}^{k} \cdot { r_{0} }^{2} - {r_{1}}^{k} \cdot { r_{1} }^{2} } \over { r_{0} - r_{1} }} & \because {r_{0}}^2 = {r_{0}} + 1, {r_{1}}^2 = {r_{1}} + 1 \\ =& {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }} \end{align*} To summarize, Fk+1=r0k+2−r1k+2r0−r1 F_{k+1} = {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }} which means, Fn=r0n+1−r1n+1r0−r1 F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} is also true when n=k+1n=k+1.

■