relation between prime number and given recurrence relation

Question

I have run into a question today. However , i stuck in it. I hope to find any help here. My question is the following

Let define a recurrence relation $\{b_n\}_0^{\infty}$ such that $b_{n+1}=2b_{n}+1$ for all $n \geq 0$. My question is that is it possible to find any $b_0$ such that all values of this recurrence relation is prime number.

My work: I thought that i should firstly find the explicit form of the given recurrence relation so using generating functional techniques , i obtained that $b_n =2^{n}b_0 +2^n -1$. I handled the combinatorics part . However , i could not derive any result claiming for a $b_0$ all $b_n$s be prime. I could only think that $2^n-1$ is always odd and $2^nb_0$ is always even for $n \geq1$ , so the values are odd for $n \geq 1$

However , i cannot explain that whether it is possible to choose any $b_0$ which make the recurrence prime for all $b_n$. Can you help me for this part

I am not sure, but I'd start with $b_n \equiv 2^n - 1 \mod b_0$ (where $b_0$, I guess supposed to be prime). Hence we have that for any value of $n$ $2^{n} - 1$ couldn't divide by $b_0$ (otherwise $b_0$ divides $b_n$). Hence, there should be two different powers of $2$ (let it be $N, M$) : $2^N \equiv 2^M \mod b_0$. Hence we have some kind of relation on $b_0$. — openspace, Nov 17 '22 at 21:19
@tonys.junior Welcome to Math SE. FYI, an Approach0 search included the AoPS thread Special sequence of primes, which contains your initial recurrence relation, the explicit form you derived, and a solution similar to my answer. Also, there's the somewhat related Existence of at least one prime for all sequences in the family of sequences. — John Omielan, Nov 17 '22 at 21:36

John Omielan · Accepted Answer · 2022-11-17T21:28:02.070

The relation is

$$b_{n} = 2^{n}b_{0} + 2^{n} - 1 = 2^{n}(b_{0} + 1) - 1 \tag{1}\label{eq1A}$$

For there to be any chance that $b_{n}$ is prime for all $n\ge 0$, we need $b_0 \ge 2$. With $b_0 = 2$, we have $b_{5} = 2^{5}(2+1)-1 = 95 = 5(19)$, which is not prime.

Thus, consider $b_0 \gt 2$. If it's not prime, we're done. Otherwise, similar to what's done in the AoPS thread Special sequence of primes, let $p = b_0$, with Fermat's little theorem then showing that

$$b_{p-1} = 2^{p-1}(b_{0}+1) - 1 \equiv 1(0 + 1) - 1 \equiv 0 \pmod{p} \tag{2}\label{eq2A}$$

However, $b_{p-1} \gt p$ means it can't be a prime.

As we've now covered all cases, we can conclude there's no integer $b_0$ such that $b_{n}$ defined in \eqref{eq1A} is a prime for all $n \ge 0$.

relation between prime number and given recurrence relation

1 Answers1