Skip to main content

Section 10.2 Some identities

We start by noting that

\begin{equation*} f_n^2- f_{n+1}f_{n-1} = f_n(f_{n-1} +f_{n-2})-f_{n+1}f_{n-1} = (f_n -f_{n+1})f_{n-1} +f_nf_{n-2}. \end{equation*}

Since \(f_{n+1} = f_n + f_{n-1}\) we have that \(f_n-f_{n+1} = -f_{n-1}\) and we get

\begin{equation*} f_n^2- f_{n+1}f_{n-1} = -f_{n-1}^2 +f_nf_{n-2} = (-1)(f_{n-1}^2 -f_nf_{n-2}). \end{equation*}

We continue in this fashion \(n-3\) more times to get

\begin{equation*} f_n^2- f_{n+1}f_{n-1} = (-1)^{n-2}(f_{2}^2 -f_3f_1)=(-1)^{n-2}(1-2\cdot 1)=(-1)^{n-1}. \end{equation*}

Note that we have

\begin{equation*} \alpha =\frac{1 + \sqrt{5}}{2} \hspace{5mm} \text{ and } \hspace{5mm} \beta=\frac{1-\sqrt{5}}{2}. \end{equation*}

And also since they satisfy \(x^2-x-1 = 0\) we have that both

\begin{equation*} \alpha^2 =\alpha+1 \hspace{5mm} \text{ and } \hspace{5mm} \beta^2=\beta+1. \end{equation*}

Thus when we multiply by \(\alpha^n\) and by \(\beta^n\) we have

\begin{equation*} \alpha^{n+2} =\alpha^{n+1}+\alpha^n \hspace{5mm} \text{ and } \hspace{5mm} \beta^{n+2}=\beta^{n+1}+\beta^n. \end{equation*}

Subtracting the second equation from the first and dividing by \(\alpha-\beta,\) we have that

\begin{equation*} \frac{\alpha^{n+2}-\beta^{n+2}}{\alpha-\beta} =\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}+\frac{\alpha^{n}-\beta^{n}}{\alpha-\beta}. \end{equation*}

Thus setting \(H_n =\frac{\alpha^n-\beta^n}{\alpha-\beta},\) the above becomes

\begin{equation*} H_{n+2}=H_{n+1}+H_n \hspace{5mm} (n\geq 1). \end{equation*}

We will show that \(H_n = f_n.\) Note that for \(\alpha\) and \(\beta\) as above, we have that

\begin{equation*} \alpha+\beta=1 \hspace{5mm} \alpha-\beta=\sqrt{5} \hspace{5mm} \alpha\beta=-1. \end{equation*}

We also have

\begin{equation*} H_1 =\frac{\alpha-\beta}{\alpha-\beta}=1 \end{equation*}

and

\begin{equation*} H_2 =\frac{\alpha^2-\beta^2}{\alpha-\beta}=\alpha+\beta=1. \end{equation*}

Since the recurrence and starting points are the same, we have that \(H_n = f_n\) and the theorem is proved.

Using Binet's formula we can partially classify what kind of primes divide some Fibonacci numbers. In fact each prime divides some Fibonacci number. Note that \(2\vert f_3, 3\vert f_4,\) and \(5\vert f_5.\) And for the rest we have the following theorem.

By Binet's formula we have that \(f_p = \frac{1}{\sqrt{5}}(\alpha^p-\beta^p).\) We use the binomial theorem to get

\begin{align*} f_p \amp=\frac{1}{2^p\sqrt{5}}\left(1+\binom{p}{1}\sqrt{5}+\binom{p}{2} 5+\binom{p}{3}5\sqrt{5}+\cdots +\binom{p}{p}5^{(p-1)/2}\sqrt{5}\right) - \frac{1}{2^p\sqrt{5}}\left(1-\binom{p}{1}\sqrt{5}+\binom{p}{2} 5-\binom{p}{3}5\sqrt{5}+\cdots - \binom{p}{p}5^{(p-1)/2}\sqrt{5}\right)\\ \amp=\frac{1}{2^{p-1}}\left(\binom{p}{1}+\binom{p}{3} 5+\cdots +\binom{p}{p}5^{(p-1)/2}\right). \end{align*}

Now since \(\binom{p}{k}\equiv 0\pmod{p}\) for \(1\leq k\leq p-1\) and \(2^{p-1}\equiv 1\pmod{p},\) we have that

\begin{equation*} f_p\equiv 2^{p-1}f_p\equiv \binom{p}{p}5^{(p-1)/2}\equiv 5^{(p-1)/2}\pmod{p}. \end{equation*}

Now by Euler's criterion, we have that

\begin{equation*} (5/p)\equiv 5^{(p-1)/2}\pmod{p}, \end{equation*}

so that

\begin{equation*} f_p\equiv \pm 1\pmod{p}, \end{equation*}

and moreover we have that

\begin{equation*} f_p^2\equiv 1\pmod{p}. \end{equation*}

With this in hand, we take the identity from the second theorem of this section, \(f^2p = f_{p-1}f_{p+1} + (-1)^{p-1},\) and note that modulo \(p\) this gives

\begin{equation*} f_{p-1}f_{p+1} \equiv 0 \pmod{p}. \end{equation*}

Thus \(p\) divides one of \(f_{p-1}\) or \(f_{p+1}.\)

Recall that from a previous theorem we have that

\begin{equation*} \gcd(f_{p-1}, f_{p+1}) = f_{\gcd(p-1,p+1)} = f_2 = 1. \end{equation*}

Thus \(p\) cannot divide both \(f_{p-1}\) and \(f_{p+1}.\)