Existence of least squares solution to $Ax=b$ Does a least squares solution to $Ax=b$ always exist?

If you think at the least squares problem geometrically, the answer is obviously "yes", by definition.
Let me try to explain why. For the sake of simplicity, assume the number of rows of $A$ is greater or equal than the number of its columns and it has full rang (i.e., its columns are linearly independent vectors). Without these hypotheses the answer is still "yes", but the explanation is a little bit more involved.
If you have a system of linear equations
$$
Ax = b \ ,
$$
you can look at it as the following equivalent problem: does the vector $b$ belong to the span of the columns of $A$? That is,
$$
Ax = b \qquad \Longleftrightarrow \qquad \exists \ x_1, \dots , x_n \quad \text{such that }\quad x_1a_1 + \dots + x_na_n = b \ .
$$
Here, $a_1, \dots , a_n$ are the columns of $A$ and $x = (x_1, \dots , x_n)^t$. If the answer is "yes", then the system has a solution. Otherwise, it hasn't.
So, in this latter case, when $b\notin \mathrm{span }(a_1, \dots , a_n)$, that is, when your system hasn't a solution, you "change" your original system for another one which by definition has a solution. Namely, you change vector $b$ for the nearest vector $b' \in \mathrm{span }(a_1, \dots , a_n)$. This nearest vector $b'$ is the orthogonal projection of $b$ onto $\mathrm{span }(a_1, \dots , a_n)$. So the least squares solution to your system is, by definition, the solution of
$$
Ax = b' \ ,  \qquad\qquad\qquad   (1)
$$
and your original system, with this change and the aforementioned hypotheses, becomes
$$
A^t A x = A^tb  \ . \qquad\qquad\qquad    (2)
$$
EDIT. Formula (1) becomes formula (2) taking into account that the matrix of the orthogonal projection onto the span of columns of $A$ is
$$
P_A = A(A^tA)^{-1}A^t \ .
$$
(See Wikipedia.)
So, $b' = P_Ab$. And, if you put this into formula (1), you get
$$
Ax = A(A^tA)^{-1}A^tb \qquad \Longrightarrow \qquad A^tAx = A^tA(A^tA)^{-1}A^tb = A^tb \ .
$$
That is, formula (2).
