Derivation of the General Term of the Fibonacci Sequence
Theorem
Let’s say that the sequence sequence $\left\{ F_{n} \right\}_{n=0}^{\infty}$ is defined as $F_{n+1} := F_{n} + F_{n-1}$. If $F_{0} = F_{1} = 1$, then for $\displaystyle r_{0} : = {{1 + \sqrt{5} } \over {2}}$ and $\displaystyle r_{1} : = {{1 - \sqrt{5} } \over {2}}$, $$ 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 $0$th 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 $$ \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, $$ {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, $$ {r_{0}}^2 = {r_{0}} + 1 \\ {r_{1}}^2 = {r_{1}} + 1 $$. Now, using mathematical induction, $$ F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $$ will be shown to be true.
When $n=0$, $$ F_{0} = {{ {r_{0}}^{0+1} - {r_{1}}^{0+1} } \over { r_{0} - r_{1} }} = 1 $$
When $n=1$, $$ F_{1} = {{ {r_{0}}^{1+1} - {r_{1}}^{1+1} } \over { r_{0} - r_{1} }} = 1 $$
Assuming when $n=k$ $$ F_{k} = {{ {r_{0}}^{k+1} - {r_{1}}^{k+1} } \over { r_{0} - r_{1} }} $$ is true,
$\left\{ F_{k} \right\}$ is the Fibonacci sequence, thus
$$ \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, $$ F_{k+1} = {{ {r_{0}}^{k+2} - {r_{1}}^{k+2} } \over { r_{0} - r_{1} }} $$ which means, $$ F_{n} = {{ {r_{0}}^{n+1} - {r_{1}}^{n+1} } \over { r_{0} - r_{1} }} $$ is also true when $n=k+1$.
■