Btukfyl

First, some definitions:

Let $A$ be a shorthand for an infinite sequence
$( a(1), a(2), a(3), dots )$
of positive integers, likewise $B$ is an infinite sequence of positive integers
$( b(1), b(2), b(3) , dots)$,
and C is an increasing infinite sequence of positive integers
$( c(0), c(1), c(2), c(3), dots)$. Call $c(0)$ the initial value of $C$.

We say that the pair $(A,B)$ is a recursion pattern for $C$ if for each
positive integer n we have
$c(n) = a(n) * c(n-1) + b(n)$. Given a recursion pattern $(A,B)$, and an
initial value for $C$, we can reconstruct all the sequence $C$.

Clearly, for any increasing infinite sequence $C$ we can find a pair $(A,B)$
which is a recursion pattern for $C$, simply by taking all the $a(n)$ to
be equal to $1$, and defining the $b(n)$ as required. If the sequence $C$ is
increasing quickly, there will be many pairs $(A,B)$ which will be
recursion patterns for $C$.

In particular, for any increasing sequence of primes, we can find
recursion patterns, many of them if the sequence grows quickly.

Now the question: can a pair $(A,B)$ be a recursion pattern for more than
one sequence of primes? In other words, given $A$ and $B$ as a recursion
pattern, is it possible there is more than one initial value for $c(0)$
which will lead to an infinite sequence of primes?

Comments:
If the answer is yes, and we can prove that, I would expect the proof
to be quite difficult. Maybe a conditional proof would be possible.
On the other hand, it may be elementary to show that the answer is no.
This question was written up by Moshe Newman.

The answer is yes, there are "recursion patterns" which result in sequences of primes for more than one choice of $c(0)$. In fact, if you are given any two "starting points", it is possible to find such sequences. The proof comes from the pigeonhole principle.

Start with $c(0), c'(0)$. These are two prime numbers with difference $d(1) := c'(0) - c(0)$. Then as the set of prime numbers is infinite, there is some pair $p_1 < p'_1$ such that $p_1 equiv p'_1 (text{mod }d)$. Let $a(1) = frac{p'_1 - p_1}{d(1)}$; let $b(1) = p_1 - a(1) c(0)$. (Note: I've slightly cheated here, and will explain the cheat at the end). Then $c(1) = a(1) c(0) + b(1) = a(1) c(0) + p_1 - a(1) c(0) = p_1$, while $c'(1) = a(1) c(0) + b(1) = frac{p'_1 - p_1}{c'(0) - c(0)} c'(0) + p_1 - frac{p'_1 - p_1}{c'(0) - c(0)} c(0) = p'_1$, as desired.

This is a pattern that can be repeated in the obvious way. We therefore have a recursion pattern that results in sequences of primes for multiple "starts".

Now for the cheat: there's no reason so far why this would make $b(i)$ positive. I don't have a completely elementary reason for that, but the prime number theorem should be enough to guarantee it. Essentially, the $n$th prime number doesn't grow "quickly enough" to escape such pairs.