Existence of some prime $x_k | k > 2$ in $x_n = x_{n-1} + x_{n-2}$ whenever $x_1$ is coprime to $x_2$

Question

It is not known whether there is a largest prime in the Fibonacci sequence, but of course there are quite a few primes.

Similarly, the Lucas sequence starting with $L_1=1, L_2 = 3$ comes to a prime at $L_4 = 7$. On the other hand, for $x_1=3, x_2 = 11$ all the $x_n$ are composite until $x_7 = 103$.

It seems intuitive that for any arbitrary positive coprime $(x_1, x_2)$ the corresponding sequence eventually arrives at a prime, but I'm wondering whether there is a proof or whether somebody out there can provide a proof. Concretely:

Given $(x_1, x_2) \in \Bbb{Z}+ : \gcd(x_1,x_2) = 1$. For all integer $n > 2$ define $x_n = x_{n-1}+x_{n-2}$. Prove that $\exists n \in \Bbb N, | n> 2 \wedge x_n \in \Bbb{P} $.

Answer 1

As Gerhard Paseman said in his comment, there are counterexamples. This is discussed in A3 of UPINT. According to the third edition, the smallest known counterexample as of the printing (in 2003) is $x_1= 8983542533631$ and $x_2 = 248272649660939$ due to John Nicol. This article by Knuth discusses the basic idea behind finding such pairs and may be a good place to start. The relevant section in UPINT has a few references in addition.