Uniqueness of general solution to SHO This may be a duplicate, though I have searched and not found this question answered, and it may also belong more on Mathematics Stack exchange than here -- in which case I'll transfer. 
My question is: how does one prove (both intuitively and rigorously) that the solution to the SHO, being a linear combination of a sine and cosine, is the most general and unique solution?
The way it is most often solved is by simply suggesting $x(t) = \exp(\Omega t)$, then solving $\Omega = \pm ik/m$, and ending up with $x(t) = A\cos(\omega t) + B\sin(\omega t)$ with $\omega = |\Omega|$. 
Suppose I am going trough this derivation with a high-school physics enthusiast, and he/she asks me "You've simply supposed $x(t)$ to be exponential, and showed that if it is, the solution is $\dots$, how do you know this is $\textit{the}$ solution?". I've done a differential equations class, and even though I passed it, I seem to have missed this crucial aspect.
EDIT
Since the posting of this question, two answers have been posted only answering the question of $\textit{how}$ the SHO should be solved. A question I did not ask. 
My question has boiled down to this; how do I show that the space of solutions of the SHO (and any 2nd order ODE) is two-dimensional? This would answer my question.
 A: Simple harmonic motion corresponds to a 2nd order differential equation. Such equations have two linearly independent solutions, and the general solution is some linear combination of these two.
A more 'thorough' but tedious algebraic treatment considers the so-called auxiliary equation of the general second order DE
$ay'' + by' + cy = 0$,
and the three possible cases (distinct real roots, repeated real roots, and conjugate complex roots) for the auxiliary function. For more detail see any introductory book that includes a section on second-order ordinary differential equations.
The general solution for the conjugate complex roots is
$y=e^{\alpha x}(c_1\cos(\beta x) + c_2\sin(\beta x))$.
SHO corresponds to the case of two conjugate complex roots (m = $\pm i\omega$), with $\alpha = 0$ and $\beta=\omega$. 
Answering your question in another way: if you guess a solution, substitute it in the DE and see that it solves it, that is a confirmation that it is a solution. Euler's formula does the rest.
EDIT: As per the comment of @KyleKanos, you may be missing the relevance of the relevant uniqueness theorem here.
A: Consider Newton's second law for a simple Hooke spring
$$ m \ddot x = -kx.$$
Below I show two ways of arriving at the general solution for this system. There are other ways of solving this. I will also note that these are not unique solutions until initial conditions have been applied.
The Intuitive Solution
Our solution to the differential equation is a function $f(t)$ that is proportional to its second derivative by a negative constant, i.e.
$$ f(t) = -\alpha \frac{d^2f}{dt^2}. $$
Both sine and cosine satisfy this, so you have to add them together to find the general solution. This approach could also let you arrive at the equally-valid solution $x(t) = c_1 e^{i\omega t} + c_2 e^{-i\omega t}$.
In my opinion, the most basic intuitive reason for superposing the solutions is that you don't know where $\sin\omega t$, $\cos\omega t$, or both is the best model until you apply your initial conditions, which provide phase information.
The Rigorous Solution
We can rearrange the differential equation to be
$$ \ddot x + \frac{k}{m}x = 0 .$$
Defining $\omega = \sqrt\frac{k}{m}$, we have $\ddot x + \omega^2x = 0$. We can apply an characteristic equation to solve our differential equation by replacing our derivatives with polynomial powers:
$$ u^2 + \omega^2 = 0 $$
$$ u = \pm i\omega. $$
The solution to a characteristic equation $u = \alpha \pm i\beta$ gives us a solution to our differential equation of
$$ x(t) = c_1e^{(\alpha + i\beta)t} + c_2e^{(\alpha - i\beta)t} = c_1 e^{\alpha t}\cos\beta t + c_2 e^{\alpha t}\sin\beta t.$$
Noting that in our case $\beta = \omega$ and $\alpha = 0$, we arrive the general solution
$$ x(t) = c_1 e^{i\omega t} + c_2 e^{-i\omega t} = A\sin\omega t + B\cos\omega t. $$
