mathschallenge.net logo

Composite Fibonacci Terms

Problem

Let $F_n$ represents the $n^{th}$ term of the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, ... .

Prove that for all composite values of $n \gt 4, F_n$ is composite.


Solution

We shall begin by proving Lemma 1: $F_{m+n} = F_{m-1}F_{n} + F_{m}F_{n+1}$.

Using this result for the two basis cases: $n = 1$ and $n = 2$ we get the following.

$n = 1: F_{m+1} = F_{m+1}F_{1} + F_{m}F_{2}$

But as $F_{1} = F_{2} = 1, F_{m+1} = F_{m-1} + F_{m}$, which is clearly true.

$n = 2: F_{m+2} = F_{m-1}F_{2} + F_{m}F_{3}$

As $F_{2} = 1$ and $F_{3} = 2, F_{m+2} = F_{m-1} + 2F_{m} = F_{m-1} + F_{m} + F_{m} = F_{m+1} + F_{m}$, which is also true.

Let us assume that Lemma 1 is true for $n = k$ and $n = k - 1$

That is, $F_{m+k} = F_{m-1}F_{k} + F_{m}F_{k+1}$ and $F_{m+k-1} = F_{m-1}F_{k-1} + F_{m}F_{k}$.

$$\begin{eqnarray}\therefore F_{m+k+1} & = & F_{m+k} + F_{m+k-1}\\& = & F_{m-1}F_{k} + F_{m}F_{k+1} + F_{m-1}F_{k-1} + F_{m}F_{k}\\& = & F_{m-1}(F_{k} + F_{k-1}) + F_{m}(F_{k+1} + F_{k})\\& = & F_{m-1}F_{k+1} + F_{m}F_{k+2}\end{eqnarray}$$

And as this is the expected result we prove that Lemma 1 is true for all values of $n$.

Now we prove Lemma 2: $F_{m} \mid F_{mn}$.

Clearly the basis case, $n = 1$, is true: $F_{1} = 1 \mid F_{mn}$.

Let us assume that $F_{m} \mid F_{mk}$.

$\therefore F_{m(k+1)} = F_{mk+k} = F_{mk-1}F_{m} + F_{mk}F_{m+1}$ (using Lemma 1)

By the induction hypothesis, $F_{m} \mid F_{mk}$, which means that $F_{m}$ divides both terms on the right hand side. Hence $F_{m} \mid F_{m(k+1)}$ and we show that $F_{m} \mid F_{mn}$ for all values of $n$.

For all composite values of $n \gt 4$, where $n = ab$, it is clear that $2 \le a, b \lt n$. Moreoever, one of $a$ or $b$ must be greater than 2. Without loss of generality let us assume that $a \gt 2$.

By Lemma 2: $F_{a} | F_{ab} = F_{n}$ and because $a \gt 2$ we know that $F_{a} \gt 1$. Hence we prove that $F_{n}$ is composite. Q.E.D.

Problem ID: 365 (03 Nov 2009)     Difficulty: 4 Star

Only Show Problem