Are there infinitely many primes of the form $k\cdot 2^n +1$?
Solution 1:
The first row of the OP's matrix is 3,5,7,..., and so obviously contains every prime except 2. More generally, Dirichlet's theorem implies that each row contains an infinite number of primes (as pointed out by marty cohen).
A Sierpinski number is a odd positive integer $k$ such that $k \cdot 2^n +1$ is composite for all $n \geq 1$. The smallest known Sierpinski number is $78557$ [the Seventeen or Bust team are trying to (computationally) prove it is the smallest]. Sierpinski showed that there are an infinite number of Sierpinski numbers, so there are an infinite number of all-composite columns in the OP's matrix (which extends zyx's answer).
Numbers of the form $k \cdot 2^n+1$ with $k<2^n$ are (sometimes) referred to as Proth numbers. Proth's Theorem gives a necessary and sufficient condition for the primality of a Proth number. Yves Gallot proth.exe is an available implementation of Proth's Theorem. Many of the largest known primes are Proth primes.
Related are numbers of the form $k \cdot 2^n-1$, for which we can detect primality via the efficient Lucas-Lehmer-Riesel test, implemented by Jean Penné's LLR. Also, there's Mersenne numbers, for which there's the giant GIMPS project searching for large Mersenne primes.
Solution 2:
Here's a simple-minded answer from simple-minded (at least in this group) me: Yes.
Use Dirichlet's theorem on primes in an arithmetic progression, for any $n$, the arithmetic progression $k 2^n+1$, $k = 1, 2, ...$ contains an infinite number of primes.
Solution 3:
There are values of $k$ for which all terms of the sequence $k.2^n + 1$ are composite. The proof uses covering congruences, starting from Euler's factorization of the fifth Fermat number; a finite set of primes is constructed and a set of congruence conditions that cover all $n$, and each condition forces divisibility by one of the primes.
There is no known value of $k$ for which it is proven that infinitely many primes exist in the sequence $k2^n + 1$.