Why can all solutions to the simple harmonic motion equation be written in terms of sines and cosines? The defining property of SHM (simple harmonic motion) is that the force experienced at any value of displacement from the mean position is directly proportional to it and is directed towards the mean position, i.e. $F=-k(x)$.
From this, 
$$m\left(\frac{d^2x}{dt^2}\right) +kx=0.$$ 
Then I read from this site

Let us interpret this equation. The second derivative of a function of x plus the function itself (times a constant) is equal to zero. Thus the second derivative of our function must have the same form as the function itself. What readily comes to mind is the sine and cosine function. 

How can we assume so plainly that it should be sin or cosine only? They do satisfy the equation, but why are they brought into the picture so directly? What  I want to ask is: why can the SHM displacement, velocity etc. be expressed in terms of sin and cosine? I know the "SHM is the projection of uniform circular motion" proof, but an algebraic proof would be appreciated.
 A: 
How can we assume so plainly that it should be sin or cosine only

It's literally just a guess. Those're obvious solutions which can be verified easily, and when they're such straightforward functions, you'll soon just be able to notice them. It's the like when you have an equation like $f'(x)=K\times f(x)$, you just see that the solutions are exponentials. After that, you know that for a differential equation like $f^{(n)}(x)=Kf(x)$ you can have upto $n$ solutions, so you aren't missing anything when you consider the sine and cosine.
It's a nice idea to not waste time/effort/space formally solving such equations when the solutions are canonical.
A: These are all good and correct answers, but I will answer from a different perspective.
Any linear-differential equation of degree $n$ has $n$ linearly independent solutions, ie. these $n$ solutions span a vector space, with sets of solutions forming a basis.
For simple harmonic motion, the differential equation is:
$$m(\dfrac{d^2x}{dt^2})+kx = 0$$
As stated in other answers, one can take the solutions to be linear combinations of $\sin(\omega t)$ and $\cos(\omega t)$, or one could take $\exp(i\omega t)$ and $\exp(-i\omega t)$. These are both sets of linearly independent functions, and both pairs solve the equation, yet they are not the same functions -  they are two different sets of basis functions.
To get from one set of solution to another, one needs to change the basis. 
A: One way of deriving it is using Taylor series (although to be fully rigorous, this requires further justification for restricting to analytic functions). We have that $f(x) = \sum a_n x^t$, so $f''(t)=\sum (n+1)(n+2)a_{n+2}t^n$. If $f''(t)=-\frac k m f(t)$, then $(n+1)(n+2)a_{n+2} = -\frac k m a_n$, so  $a_{n+2} = \frac {-k a_n}{(n+1)(n+2)m}$. So $a_0$ determines $a_2$, which determines $a_4$, etc., and $a_1$ determines $a_3$ which determines $a_5$, and so on. Since all of the even terms vary linearly based on the 0th term, and don't depend on the odd terms, and vice versa for the odd terms, we can find a solution $f_0$ by taking $a_0=1, a_1=0$ and $f_1$ from $a_0=0, a_1=1$, and all solutions will be a linear combination of $f_0$ and $f_1$. And if you work out what those solutions are, they correspond to cosine and sine, respectively.
You can also get to sine and cosine by taking $f(t)=e^{at}$. Then $f''(t)=a^2e^{at}$, so if $f'' = -\frac km f$, then $a^2= -\frac km$. This leads to the two solutions $a = \pm i\sqrt{\frac km}$. Neither root gives a real solution, but $f(x) = \frac 12 (e^{ct} + e^{-ct})$ and $f(x) = \frac 1{2i} (e^{ct} - e^{-ct})$, where $c = i\sqrt{\frac km}$, do. Those correspond to cosine and sine.
A: This follows from the uniqueness theorem for solutions of ordinary differential equations, which states that for a homogeneous linear ordinary differential equation of order $n$, there are at most $n$ linearly independent solutions.
The upshot of that is that if you have a second-order ODE (like, say, the one for the harmonic oscillator) and you can construct, through whatever means you can come up with, two linearly-independent solutions, then you're guaranteed that any solution of the equation will be a linear combination of your two solutions.
Thus, it doesn't matter at all how it is that you come to the proposal of $\sin(\omega t)$ and $\cos(\omega t)$ as prospective solutions: all you need to do is 


*

*verify that they are solutions, i.e. just plug them into the derivatives and see if the result is identically zero; and

*check that they're linearly independent.


Once you do that, the details of how you built your solutions become completely irrelevant. Because of this, I (and many others) generally refer to this as the Method of Divine Inspiration: I can just tell you that the solution came to me in a dream, handed over by a flying mass of spaghetti, and $-$ no matter how contrived or elaborate the solution looks $-$ if it passes the two criteria above, the fact that it is the solution is bulletproof, and no further explanation of how it was built is required.
If this framework is unclear or unfamiliar, then you should sit down with an introductory textbook on differential equations. There's a substantial bit of background that makes this sort of thing clearer, and which simply doesn't fit within this site's format.
