Mersenne, Fibonacci... are there other cases in which the existence of a given prime implies the existence of another prime? Thinking about why it seems impossible to find a case in which the existence of a given prime implies the existence of another bigger prime, I tried to make a list of cases in which knowing that a number is prime then automatically we know that other one is prime. So far I just can recall two well known non-trivial situations:


*

*Mersenne numbers, if $p=2^n-1$ is prime then $n$ is prime as well. The opposite is not true.


*Fibonacci numbers, if $p=F_n$ is prime then $n$ is prime as well. The opposite is not true.

In both cases $n$ is smaller than $p$.
I would like to ask the following questions:


*

*Did I forget more cases?


*It seems that the existence of the bigger prime $p$ implies the existence of the smaller prime $n$ but I can not recall any cases in which a single (only one required) smaller prime $n$ implies that a bigger prime $p$ automatically exists. Are there any papers regarding that impossibility? Are there such cases?
Thank you!

Update 16/02/2016: as kindly explained in the comments by @DanielFischer and answer by @TitoPiezasIII, there are generalizations of both the Mersenne and Fibonacci numbers that are also part of the list.
 A: There seems to be infinitely more such sequences. 

I. Particular

Starting with $n=0$, note that for the Fibonacci numbers,
$$F_n = 0,1,1,2,\color{red}3,5,8,13,\dots\tag1$$
and $F_4=3$ does not have a prime index. Similarly for the Jacobsthal numbers,
$$J_n = 0, 1, 1, 3, \color{red}5, 11, 21, 43,\dots\tag2$$
with the similar exception $J_4=5$. (Indices for prime $J_n$ is A107036.). We also have the Pell numbers,
$$P_n = 0, 1, 2, 5, 12, 29, 70, 169,\dots\tag3$$
and if $P_n$ is prime, then $n$ is prime.

II. General

If we define the first family of the Lucas sequence, 
$$U_n(P,Q) \equiv \frac{a^n-b^n}{a-b}$$
where $a,b$ are the roots of $x^2-Px+Q=0$, then,
$$U_n(1,-1) = \text{Fibonacci}\\
U_n(1,-2) = \text{Jacobsthal}\\
U_n(1,-3) = \text{A006130}\\
\vdots\\
U_n(2,-1) = \text{Pell}\\
U_n(3,-1) = \text{A006190}\\\vdots$$
so presumably appropriate members of the family behave similarly.
A: There is a prime-generating formula, but not a practical one.
Ghandhi's formula for the next prime: Let $Q$ be the product of the primes less than the odd prime $p$.(If $p=3$ then $Q=2.$)$$\text {Let }\quad S=-\frac {1}{2}+\sum_{d|Q}\frac {\mu (d)}{2^d-1}$$ where $\mu$ is the Mobius function.$$\text {Then }\quad 1<2^pS<2.$$ Since $2^{p-1}<1$ and $2<2^{p+1}$ this uniquely defines the natural number $p$.
To prove it write each term $\mu (d)/(2^d-1)=\mu (d)\sum_{n=1}^{\infty}2^{-n d}.$ Collect powers of $2$ in the sum over $d|Q.$ Using the property of $\mu$ that $\sum_{e|n}\mu(e)=0$ for $n>1$ we obtain $$S=\sum_{n\in T}2^{-n}$$ where $T=\{m:m>1\land \gcd (m,Q)=1\}.$  From the def'n of $Q$ we have $\min T=p$, and all members of $T$ are odd, so $$2^{-p}<S\leq 2^{-p}(1+1/2^2+1/2^4+...)=2^{-p}(4/3)<2^{1-p}.$$
This is about as inefficient a way as possible for generating primes.E.g. to to find the least prime greater than $1,000,000$ with this formula, you need to know all the primes less than $1,000,000$, and sum all the terms in the formula. Since there are about $72,000$ primes below $1,000,000$ this means adding about $2^{72,000}$ terms to get $S$. 
