How do we know $\sin$ and $\cos$ are the only solutions to $y'' = -y$?

One way to show uniqueness is the following:

$\textbf{Theorem:}$ A second order differential equation of the form $y''+P(x)y'+Q(x)y=0$ has at most two linearly independent solutions.

$\text{Sketch of Proof: }$ 1) Define the Wronskian determinant as $\det W_3$ where:$$W_3=\begin{bmatrix}y_1 &y_2 &y_3\\y_1' &y_2' &y_3'\\y_1'' &y_2'' &y_3''\end{bmatrix}$$ Here the $y_i$'s solve the aforementioned equation.

2. Show that

$$\exists ~c_i:\sum_{i=1}^3c_iy_i=0\iff \det W_3=0$$

3. Since $y_i''=-P(x)y_i'-Q(x)y_i$, line 3 is a linear combination of lines 1 and 2. Thus the matrix does not have full column rank and it's determinant is zero, and hence the 3 functions have to be linearly dependent.

You can use this theorem as follows: If you find two linearly independent solutions to a linear second order ODE, then every solution to that ODE can be expressed as a linear combination of those two. In your case, you know $\sin x, \cos x$ are solutions and you need to look no further, since they are linearly independent (calculate $W_2$ and it is non-zero).

For the particular case considered, one can also solve the equation using quadrature and obtain a general solution that looks like $y(x)=C_1\sin x+C_2 \cos x$.

EDIT: Proof of Lemma 2

To answer @blue 's comment completely, it is true that the proof of that statement is not JUST linear algebra, but in my opinion, it is still pretty easy to prove with no other machinery to be used other than the fact that a function that has zero derivative is constant. Here is a way that can be used to show both directions:

Specifically, let us assume that $\det W_3=0$ and also that all the $2\times 2$ sub-Wronskians between any two functions of the set $\{y_1,y_2,y_3\}$ are non-zero (if any of them were, then there would exist non-zero $c_i$'s that render the functions linearly dependent hence making the Wronskian vanish trivially).In this case, with

$T_{ij}=y'_iy_j-y'_jy_i=y_j^2\left(\frac{y_i}{y_j}\right)'\neq 0$

it can be easily shown that, after some algebraic simplifications: $$\left(\frac{T_{31}}{T_{21}}\right)'=y_1\det W_3$$

which yields that $T_{31}=AT_{21}$ for some non-zero constant $A$. This in turn can be manipulated, using the identity above, into the form

$$\left(\frac{y_3}{y_1}\right)'-A\left(\frac{y_2}{y_1}\right)'=0\iff y_3-Ay_2-By_1=0$$

and hence there exist non-zero constants that render the functions linearly independent.

Note: We had to assume in the above proof that all sub-Wronskians are non-vanishing. This is the reason why proofs involving Wronskians are usually inductive in the dimension of the linear vector space. If a sub-Wronskian is zero, it is trivial to see that the determinant of the Wronskian will be zero if one has proven it for all dimensions smaller than that. The only non-trivial case can be shown as above for any dimension $n$.

Without the need for other technology, it follows from the existence and uniqueness theorem for solutions of differential equations (Cauchy-Lipschitz, or Picard-Lindelöf, according to sources) in $\mathbb{R}^n$. Write the system in the linearized form $$ \begin{cases} y'=z\\ z' = -y \end{cases} $$ (this is clearly equivalent to $y''=-y$, after introducing an auxiliary variable).

Let $y(x)$ (together with $z(x)=y'(x)$) be any solution of this system of differential equations with initial values $y(0)=y_0,z(0)=z_0$.

Then, you can find $c_1,c_2$ such that the function $\hat{y}(x) = c_1 \sin x + c_2 \cos x$ solves the differential equation and has the same initial conditions $\hat{y}(0)=y_0, \hat{y}'(0) = z_0$. Hence, by the uniqueness theorem, $y(x)=\hat{y}(x)$, which is the result you need.

Starting from $y'' = -y$, we can add $y$ to form

$$y'' + y = 0$$

This is a homogeneous second order linear differential equation which we can simplify by writing the characteristic polynomial as

$$r^2 + 1 = 0$$

or

$$r = \pm i$$

which are distinct roots. The general solution can be written as

$$y(x) = c_1\sin(x) + c_2\cos(x)$$

This tells us that $y_1 = \sin(x)$ is a solution and so is any constant multiple of it, such as $c_1\sin(x)$. Similarly, $y_2 = \cos(x)$ is another solution (and so is any function of the form $c_2\cos(x)$). So, by the principle of superposition, we can add $c_1\sin(x)$ and $c_2\cos(x)$ to form the general solution.

As any linear combination of $c_1\sin(x)$ + $c_2\cos(x)$ works, it is clear that $\sin(x)$ and $\cos(x)$ cannot be the only solutions.

---

Principle of Superposition: If $y_1$ and $y_2$ are any two solutions of the homogeneous equation $y′′ + p(x)y′ + q(x)y = 0$. Then any function of the form $y = c_1 y_1 + c_2 y_2$ is also a solution of the equation, for any pair of constants $c_1$ and $c_2$.

Remark: However, while the general solution of $y′′ + p(x)y′ + q(x)y = 0$ will always be in the form of $c_1 y_1 + c_2 y_2$, where $y_1$ and $y_2$ are some solutions of the equation, the converse is not always true. Not every pair of solutions $y_1$ and $y_2$ could be used to give a general solution in the form $y = c_1 y_1 + c_2 y_2$.

You claim that $\sin(x)$ and $\cos(x)$ are the only solutions. Instead, you should focus on linear combinations of these:

$$ y_1 = \cos(x)$$ $$ y_2 = \sin(x)$$ $$ y_3 = \sin(x) + \cos(x)$$ $$ y_4 = 2\sin(x) + 3\cos(x)$$ $$ y_5 = \sin(x) + i\cos(x)$$ $$ y_6 = 10\sin(x) - 11i\cos(x)$$

among many others where $y_i = c_1\sin(x) + c_2\cos(x)$ for constant $c_1,c_2$.