<s>[INST] Does iterating $n \to 2n+1$ always eventually produce a prime number? Is it the case that for every non-negative integer $n$, iterating $n \to 2n+1$ eventually produces a prime number? (This is the same as asking whether for every positive integer $n$, there is a non-negative integer $k$ such that $2^k n  - 1$ is prime.) If this is not settled by proof, is there some heuristic argument either way?
 [/INST] (Following up on the connection to Riesel numbers mentioned in other answers ...)
For an infinite set of counterexamples, here is a proof-sketch (adapted from Baczkowski, et al.) showing that 
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73} \implies \forall k\in \mathbb{N}\  \big(f^k(n-1) \text{ is composite}\big),$$ where $f:\mathbb{N}\to\mathbb{Z}^+:n\mapsto 2n+1$ and $f^k$ is the $k$-fold iteration of $f$.  
Note that since $f^k(n-1) = n\cdot 2^k - 1$ for $n\in\mathbb{Z}^+$, the above is equivalent to
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73} \implies \forall k\in \mathbb{N}\  \big(n\cdot 2^k-1 \text{ is composite}\big),$$
which is to say that all such $n$ are Riesel numbers. 
The following congruence classes are sufficient for this purpose: 
$$\text{congruence classes for }k\text{ and }n\\
\begin{array}{|c|c|} 
k\equiv a_i\pmod{m_i} & n\equiv b_i\pmod{p_i} \\
\hline
0\pmod{2} & 1\pmod{3} \\
0\pmod{3} & 1\pmod{7} \\
1\pmod{4} & 3\pmod{5} \\
11\pmod{12} & 2\pmod{13} \\
7\pmod{36} & 4\pmod{73} \\
19\pmod{36} & 18\pmod{37} \\
31\pmod{36} & 13\pmod{19}
\end{array}
$$
As can be directly verified, the entries in the above table have the following properties:


*

*The congruence classes for $k$ form a covering system for the integers; i.e., every integer $k$ satisfies at least one of the congruences $k\equiv a_i\pmod{m_i}$. (To verify this, it is necessary to check only $k\in \{0,1,2,\dots,35 \}$, because $36$ is the least common multiple of the moduli $\{2,3,4,12,36\}$.)

*The congruences are such that in each row $i\ (1\le i\le 7)$, $b_i\cdot 2^{a_i} \equiv 2^{m_i} \equiv 1\pmod{p_i}$. Consequently, for all $i\ (1\le i\le 7)$
$$k\equiv a_i\pmod{m_i}\quad \& \quad n\equiv b_i\pmod{p_i}\\ \implies\ n\cdot2^k \equiv b_i\cdot 2^{a_i+r\cdot m_i} \equiv (b_i\cdot 2^{a_i})(2^{m_i})^r \equiv 1 \pmod{p_i}.$$ 
Now, by the Chinese Remainder Theorem, there exist simultaneous solutions to all seven of the congruences for $n$; in particular, the Extended Euclidean Algorithm yields the solutions 
$$n \equiv 33737173 \pmod{3\cdot 5\cdot 7\cdot 13\cdot 19\cdot 37\cdot 73}.$$
Therefore, for every such $n$, 
$$\forall k\in \mathbb{N}\  \big(n\cdot2^k-1\text{ has at least one divisor in the set }\{3,5,7,13,19,37,73  \}\big).\quad\quad\text{QED}$$
</s>