How do we know Euclid's sequence always generates a new prime? How do we know that $(p_1 \cdot \ldots \cdot p_k)+1$ is always prime, for $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, $\ldots$ (i.e., the first $k$ prime numbers)?
Euclid's proof that there is no maximum prime number seems to assume this is true.

Euclid's proof does not deduce that $\,N = 1+p_1\cdots p_k\,$ is prime. Rather, Euclid's proof deduces that $\,N\,$ is coprime to all $\,p_i,\,$ so the prime factors of $\,N\,$ cannot include any $\,p_i.\,$ But since $\,N> 1\,$ it has some prime factor $\,p\,$ (e.g. its least factor $> 1),\,$ which yields a prime $p$ distinct from all $\,p_i$
The key idea is not that Euclid's sequence $\ f_1 = 2,\,\ \color{#0a0}{f_{n}} = \,\color{#c00}{\bf 1} + f_1\cdots f_{n-1}$ is an infinite sequence of primes but, rather, that it is an infinite sequence of coprimes, i.e. $\,{\rm gcd}(f_n,f_k) = 1\,$ when $\,n>k,\,$ since then any common divisor of $\,\color{#0a0}{f_n},\,\color{#b0f}{f_k}\,$ must divide 
$\ \color{#c00}{\bf 1} = \color{#0a0}{f_n} - f_1\cdots \color{#b0f}{f_k}\cdots f_{n-1}.$
Any infinite sequence $\,f_n > 1 \,$ of coprimes  yields an infinite sequence of distinct primes $\, p_n $ obtained by choosing $\,p_n$ to be any prime factor of $\,f_n,\,$ e.g. the least prime factor.  
Remark $\ $ This misunderstanding often arises from reading a proof of Euclid's result reformulated to be by contradiction (which was not used by Euclid). In one form, it can be deduced that if there are only finitely many primes $\,p_1,\ldots p_k,\,$ then $\,n = 1+p_1\cdots p_k\,$ is prime, because  $\,n > 1\,$  has no smaller prime factors. But this does not imply that $\,n\,$ is actually prime because the deduction depends on the hypothesis that there are only finitely many primes, which is false in the (actual) natural numbers $\,\Bbb N.\,$ Because the proof by contradiction  is carried out in the hypothetical universe "$\Bbb N$ with finitely many primes", one cannot apply any of its conclusions to the (actual) universe $\Bbb N.\,$ It is the nature of proofs by contradiction that one can deduce all sorts of nonintuitive results. When this occurs in a universe like $\,\Bbb N\,$ where we have very strong  intuition, it can be quite challenging to keep things straight. 
