# Proving that there are infinitely-many prime numbers that are not Fibonacci numbers

Fibonacci numbers $$\{F_n\}_n\in\mathbb{N}$$ are defined by the sequence $$F_{n+2}=F_{n+1}+F_{n}$$, $$F_1=F_2=1$$. Now prove that there are infinitely many prime numbers which are not Fibonacci numbers.

I tried very much and tried to get a proof by contradiction, but failed. I assumed the negation, but it takes me nowhere.

I assumed that there is a prime number which is a Fibonacci number and the next prime is also a Fibonacci number. Hence, as there is at least one prime between $$n$$ and $$2n$$, then $$2n$$ will have a Fibonacci number form, which can be hence expressed as a prime. But I am not sure what to do next. Is my assumption correct after all?

• Why the negative reactions ? The question is clear and an effort is shown. – Peter Jan 20 '19 at 14:48
• yes that is what i am thinking – user636268 Jan 20 '19 at 14:52

Analyzing mod $$11$$, you can show that no fibonacci-number has the form $$11k+4$$, but infinite many primes have that form because of Dirichlet's theorem.
• One can easily prove (by induction or otherwise) the identities $$F_{2n} = (F_{n-1} + F_{n+1}) F_n,$$ $$F_{2n-1} = F^2_n + F^2_{n-1}.$$ From the first identity, $F_{2n}$ is never prime for $n > 2$. From the second identity, if $F_{2n-1} = p$ is prime, then it is a sum of squares, which forces $p = 2$ or $p \equiv 1 \bmod 4$. So the only prime $F_n$ are either $F_3 = 2$, $F_4 = 3$, or are $1 \bmod 4$. But there are infinitely many primes of the form $3 \bmod 4$ (take $4$ times the product of all such primes and then subtract one; this number has a new prime factor of this form). – Lorem Ipsum Jan 21 '19 at 0:14
Let us assume to the contrary that only finitely many primes are not Fibonacci numbers. Suppose the largest of them is $$p_{k}$$. Then for every n>k, $$p_{n}$$ must be some Fibonacci number. Now we know, $$F_{2n+1}= F_{2n}+F_{2n-1}> F_{2n-1}+F_{2n-1}=2F_{2n-1}$$ or, $$F_{2n+1}>2F_{2n-1}$$
Now we know there exists at least 1 prime between n and 2n. So, there must exist a prime between $$F_{2n-1}$$ and $$2F_{2n-1}$$. Therefore, there should exist a prime between $$F_{2n+1}$$ and $$F_{2n-1}$$ .
Now, suppose the prime be $$p_{n}$$ where n>k. So, according to our assumption $$p_{n}$$ is a fibonacci number. And $$p_{n}$$ lies between $$F_{2n-1}$$ and $$F_{2n+1}$$. So, $$p_{n}$$ must be $$F_{2n}$$. But for any n in N, $$F_{2n} = (F_{n-1} + F_{n+1})F_{n}$$ . Hence, $$F_{2n}$$ cannot be a prime. So, we reach a contradiction. [Hence, proved]