Existence and uniqueness of the natural cubic spline

Step 1 (unknowns: the second derivatives at the knots). Let $M_i = S''(x_i)$ for $i=0,\dots,n$. The natural boundary conditions fix $M_0=0$ and $M_n=0$ immediately, leaving $n-1$ unknowns $M_1,\dots,M_{n-1}$ to determine.

Step 2 (reconstruct each cubic piece from its M values). On $[x_i,x_{i+1}]$, since $S$ is cubic, $S''$ is linear, so it must be the straight line through $(x_i,M_i)$ and $(x_{i+1},M_{i+1})$. Integrating this linear function twice and fixing the two constants of integration using $S(x_i)=y_i$ and $S(x_{i+1})=y_{i+1}$ determines $S$ completely on that piece, in terms of $M_i, M_{i+1}, y_i, y_{i+1}$ and the spacing $h_i=x_{i+1}-x_i$. So once all the $M_i$ are known, $S$ is fully known.

Step 3 (matching slopes gives a linear system). By construction $S$ and $S''$ are already continuous across each knot. Demanding that the first derivative $S'$ also matches from both sides at each interior knot $x_i$ ($i=1,\dots,n-1$) produces one linear equation per interior knot relating three consecutive unknowns: $h_{i-1} M_{i-1} + 2(h_{i-1}+h_i) M_i + h_i M_{i+1} = 6\left(\dfrac{y_{i+1}-y_i}{h_i} - \dfrac{y_i-y_{i-1}}{h_{i-1}}\right)$. This gives $n-1$ linear equations in the $n-1$ unknowns $M_1,\dots,M_{n-1}$ (using $M_0=M_n=0$).

Step 4 (the system has a unique solution). The coefficient matrix of this system is tridiagonal with diagonal entries $2(h_{i-1}+h_i)$ and off-diagonal entries $h_{i-1}$ and $h_i$; since $2(h_{i-1}+h_i) > h_{i-1}+h_i$ (as all spacings $h_i>0$), the matrix is strictly diagonally dominant, and a strictly diagonally dominant matrix is always invertible. So the linear system for $M_1,\dots,M_{n-1}$ has exactly one solution, and by Step 2 this determines exactly one spline $S$, proving both existence and uniqueness.