In mathematics, Fibonacci sequence is a sequence of positive integers
$$a_{1}, a_{2}, a_{3},\cdots a_{n} $$
which satisfies the following conditions
\begin{enumerate}
\item $a_{1}=1$,
\item $a_{1}=1$,
\item $a_{n}=a_{n-1}+a_{n-2}, \forall n \geqslant 2$
\end{enumerate}
This is a recurrence relation and we need to find out a general formula to denote every single member of the sequence.
There are many ways to solve for this question. For example, a combinatorial expert may define a generating function $F(x)=\sum^{\infty}_{n=1} a_{n}x^{n}$ where $a_{i}$ is a Fibonacci number.\footnote{For a detailed proof of this method, refer to Richard Brualdi's \textit{Introductory Combinatorics}, 5th edition.} By solve for $F(x)$ explicitly, we can write out the general formula of the sequence: $${a_{n}=(\frac{1}{\sqrt{5}})(\frac{1-\sqrt{5}}{2})^{n}-\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n}}$$.
Another widely recognized proof uses matrix. By noticing the recurrence relation is a linear difference equation, we can set up a two-dimensional system
\[
\left( \begin{array}{r} a_{n+2} \\ a_{n+1} \end{array}\right)= \left( \begin{array}{rr} 1 & 1 \\ 1 & 0 \end{array}\right)\times \left( \begin{array}{r} a_{n+1} \\ a_{n} \end{array}\right).
\]
Using eigenvalues and respective eigenvectors of this system, we can also get the same general formula of the sequence. \footnote{For a more detailed proof, refer to Henry Gould (1981)}
In this post, I will use another method to prove the sequence's general formula. The methodis conceptually straightforward and requires no further knowledge than basic geometric sequence properties and undetermined coefficient calculation. In specific, I will construct a couple of geometric sequences from the relation $a_{n}=a_{n-1}+a_{n-2}$, calculate their general formulas, and combine them to get the final result.
First of all, we know that for a geometric sequence {$b_{n}$}, if $b_{1}=k$ and its recurrence relation is $b_{n}=mb_{n-1}$, ($k \in \mathbb{R}, m \in \mathbb{R}$), then we know $b_{n}=k m^{n-1}$.
Given the recurrence relation $a_{n}=a_{n-1}+a_{n-2}, n \geqslant 3$, it is possible to rewrite this equation and construct a geometric sequence, and by writing out its general formula, we are one step closer to calculating the general form of Fibonacci numbers.
Rewrite $a_{n}=a_{n-1}+a_{n-2}$ to be $a_{n}+y(a_{n-1})=x(a_{n-1}+ya_{n-2})$, and this implies that if we can find real numbers $x$ and $y$ to make the two equations identical, then the sequence ${a_{n}+ya_{n-1}}$ is a geometric sequence with common ratio $x$.
After some calculations, we can get $a_{n}+y(a_{n-1})=x(a_{n-1}+ya_{n-2})$ is $a_{n}=(x-y)a_{n-1}+xya_{n}$, and thus it is obvious that \begin{subequations}
\begin{align}
x-y &= 1,\\
xy &= 1,
\end{align}
\end{subequations}
Thus, $x=\frac{-1 \pm \sqrt{5}}{2}$ and $y=\frac{1 \pm \sqrt{5}}{2}$. We choose $x$ to be $\frac{1+\sqrt{5}}{2}$, and $y$ is $\frac{-1+\sqrt{5}}{2}$ correspondingly \footnote{Choosing the other bundle yields the same final result.}.
Now that $a_{n}+\frac{-1+\sqrt{5}}{2}(a_{n-1})=\frac{1+\sqrt{5}}{2}(a_{n-1}+\frac{-1+\sqrt{5}}{2}(a_{n-2}))$, we can see that $a_{n+1}+\frac{-1+\sqrt{5}}{2}(a_{n})$ is a geometric sequence whose initial term is $1+\frac{-1+\sqrt{5}}{2}=\frac{1+\sqrt{5}}{2}$ and common ratio is $\frac{1+\sqrt{5}}{2}$. So $$a_{n+1}+\frac{-1+\sqrt{5}}{2}(a_{n})=(\frac{1+\sqrt{5}}{2})^n.$$
Seeing that the strategy of constructing geometric sequence works in the first stage, we might be attempted to do it again to the above recurrence relation. However, it is important to note that the right hand side term is no longer a constant; instead, it is also related to $n$. Thus, we need to add rewrite the relation slightly differently.
Let $a_{n+1}+\lambda (\frac{1+\sqrt{5}}{2})^{n+1}=\frac{1-\sqrt{5}}{2}(a_{n}+\lambda (\frac{1+\sqrt{5}}{2})^{n})$, and compare it to the original equation $a_{n+1}+\frac{-1+\sqrt{5}}{2}(a_{n})=(\frac{1+\sqrt{5}}{2})^n$, we know to equalize the two equations, it must be the case that $$\lambda (\frac{1-\sqrt{5}}{2}) (\frac{1+\sqrt{5}}{2})^{n}-\lambda (\frac{1+\sqrt{5}}{2})^{n+1}=(\frac{1+\sqrt{5}}{2})^{n}$$
After some computation work, we can get that $\lambda=-\frac{1}{\sqrt{5}}$. Plug it back in the recurrence relation, we get $$a_{n+1}-\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n+1}=\frac{1-\sqrt{5}}{2}(a_{n}-\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n})$$
Although it looks a little bit ugly, actually the sequence ${a_{n}-\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n}}$ is a geometric sequence with initial term $\frac{5-\sqrt{5}}{10}$ and common ratio $\frac{1-\sqrt{5}}{2}$. So $${a_{n}-\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n}}=(\frac{5-\sqrt{5}}{10})(\frac{1-\sqrt{5}}{2})^{n-1}$$.
Note that $\frac{5-\sqrt{5}}{10}=(\frac{1}{\sqrt{5}})(\frac{1-\sqrt{5}}{2}).$ If we rewrite the equation, then $${a_{n}=(\frac{1}{\sqrt{5}})(\frac{1-\sqrt{5}}{2})^{n}-\frac{1}{\sqrt{5}} (\frac{1+\sqrt{5}}{2})^{n}}$$
and this is the exact general formula of Fibonacci sequence.
My method stems from realization that potential geometric sequences might be derived from the given recurrence relation, and since we are more familiar with geometric sequence's properties, we can use it to tackle more complicated problems. The method is conceptually naive and requires the original relations to be simple. Otherwise, we may resort to other techniques like generating functions.
REFERENCE
1. Brualdi, Richard, \textit{Introductory Combinatorics, 5th edition}
2. Gould, Henry \textit{A History of the Fibonacci Q-Matrix and a Higher-dimensional Problem}, Fibonacci Quart., 19(1981), 250-257
