On this page $\mathbb{P}$ denotes a vector space of all polynomials over the field of real numbers $\mathbb{R}$. By $\mathbb{N}$ we denote the set of positive integers.
Proof.
By the definition of a $2\times2$ determinant the theorem is true for $n=1$:
\[
\left| \begin{array}{cc}
1 & x_0 \\
1 & x_1 \end{array} \right| =
x_1 - x_0.
\]
To illustrate the general proof, we will start with the proof for the case $n=2$. We use column operations on the determinant to reduce the $3\times3$ determinant to the $2\times2$ determinant as follows:
\begin{alignat*}{2}
\left| \begin{array}{ccc}
1 & x_0 & x_0^2 \\
1 & x_1 & x_1^2 \\
1 & x_2 & x_2^2
\end{array} \right|
& = \left| \begin{array}{ccc}
1 & x_0 & x_0^2 - x_0^2 \\
1 & x_1 & x_1^2 - x_1 x_0 \\
1 & x_2 & x_2^2 - x_2 x_0
\end{array} \right| & & \quad
\small{\text{multiply the 2nd column by $x_0$ and subtract from the 3rd}}\\[5pt]
& = \left| \begin{array}{ccc}
1 & x_0 & 0 \\
1 & x_1 & x_1 (x_1 -x_0) \\
1 & x_2 & x_2(x_2 -x_0)
\end{array} \right| & & \quad \small{\text{do algebra}} \\[5pt]
& = \left| \begin{array}{ccc}
1 & x_0 - x_0 & 0 \\
1 & x_1 - x_0 & x_1 (x_1 -x_0) \\
1 & x_2 - x_0 & x_2(x_2 -x_0)
\end{array} \right| & & \quad
\small{\text{multiply the 1st column by $x_0$ and subtract from the 2nd}} \\[5pt]
& = \left| \begin{array}{ccc}
1 & 0 & 0 \\
1 & x_1 - x_0 & x_1 (x_1 -x_0) \\
1 & x_2 - x_0 & x_2(x_2 -x_0)
\end{array} \right| & & \quad \small{\text{do algebra}} \\[5pt]
& = 1 \, \left| \begin{array}{cc}
x_1 - x_0 & x_1 (x_1 -x_0) \\
x_2 - x_0 & x_2(x_2 -x_0)
\end{array} \right| & & \quad \small{\text{expand along the 1st row}} \\[5pt]
& = (x_1 - x_0) (x_2 -x_0) \left| \begin{array}{cc}
1 & x_1 \\
1 & x_2
\end{array} \right| & & \quad \small{\text{factor out the common factor in each row}} \\[5pt]
& =(x_2 -x_0) (x_1 - x_0) (x_2 - x_1) & &
\end{alignat*}
The method of proof for the $(n+1)\times(n+1)$ determinant is identical to the preceding special case. We just have to apply the method $n-1$ times to reach the $2\times2$ determinant and after that get the algebraic expression for the original determinant. Here is the reasoning. The value of the determinant
\[
\left| \begin{array}{cccccc}
1 & x_0 & x_0^2 & \cdots & x_0^{n-1} & x_0^n \\
1 & x_1 & x_1^2 & \cdots & x_1^{n-1} & x_1^n \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
1 & x_{n-1} & x_{n-1}^2 & \cdots & x_{n-1}^{n-1} & x_{n-1}^n \\
1 & x_n & x_n^2 & \cdots & x_n^{n-1} & x_n^n
\end{array} \right|
\]
will not change if we do the following: For $k \in \{2,\ldots,n+1\}$ replace the $k$th column by the column obtained by subtracting $(k-1)$st column from the $k$th column. We get the following determinant with the same value as the given one
\[
\left| \begin{array}{cccccc}
1 & 0 & 0 & \cdots & 0 & 0 \\
1 & x_1 - x_0 & x_1^2 - x_1 x_0 & \cdots & x_1^{n-1} - x_1^{n-2} x_0 & x_1^n - x_1^{n-1} x_0 \\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
1 & x_{n-1} - x_0 & x_{n-1}^2 - x_{n-1}x_0 & \cdots & x_{n-1}^{n-1} -x_{n-1}^{n-2} x_0 & x_{n-1}^n - x_{n-1}^{n-1}x_0 \\
1 & x_n - x_0 & x_n^2 - x_n x_0 & \cdots & x_n^{n-1} - x_{n}^{n-2}x_0 & x_n^n - x_{n}^{n-1}x_0
\end{array} \right| .
\]
We expand this determinant along the 1st row and simplify entries to get
\[
\left| \begin{array}{ccccc}
x_1 - x_0 & x_1(x_1 - x_0) & \cdots & x_1^{n-2}(x_1 - x_0) & x_1^{n-1}(x_1 - x_0) \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
x_{n-1} - x_0 & x_{n-1}(x_{n-1} - x_0) & \cdots & x_{n-1}^{n-2}(x_{n-1} - x_0) & x_{n-1}^{n-1}(x_{n-1} - x_0) \\
x_n - x_0 & x_n(x_n - x_0) & \cdots & x_{n}^{n-2}(x_n - x_0) & x_{n}^{n-1}(x_n - x_0)
\end{array} \right| .
\]
Next, we factor out of the determinant the common factor present along each row to get
\[
(x_n - x_0)(x_{n-1} - x_0) \cdots (x_1 - x_0) \left| \begin{array}{ccccc}
1 & x_1 & \cdots & x_1^{n-2} & x_1^{n-1} \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
1 & x_{n-1} & \cdots & x_{n-1}^{n-2} & x_{n-1}^{n-1} \\
1 & x_n & \cdots & x_{n}^{n-2} & x_{n}^{n-1}
\end{array} \right|.
\]
Notice that we started by the $(n+1)\times(n+1)$ determinant and the size of the determinant in the preceding expression is $n\times n$. We evaluate the preceding determinant by repeating the same procedure that we did above. We get additional factors in the product and the smaller determinant:
\[
\left(\prod_{k=2}^n \bigl( x_k - x_1 \bigr) \right) \left(
\prod_{k=1}^n \bigl( x_k - x_0 \bigr) \right) \left| \begin{array}{cccc}
1 & x_2 & \cdots & x_2^{n-2} \\
\vdots & \vdots & \ddots & \vdots \\
1 & x_{n-1} & \cdots & x_{n-1}^{n-2} \\
1 & x_n & \cdots & x_{n}^{n-2}
\end{array} \right| .
\]
Notice that the size of the preceding determinant is $(n-1)\times (n-1)$. Repeating this procedure for the total of $n-1$ times, the given $(n+1)\times(n+1)$ determinant evaluates to the following expression
\[
\prod_{j=0}^{n-2} \left(
\prod_{k=j+1}^n \bigl( x_k - x_j \bigr) \right) \left| \begin{array}{cc}
1 & x_{n-1} \\
1 & x_n
\end{array} \right|,
\]
which further equals to
\[
\prod_{j=0}^{n-1} \left(
\prod_{k=j+1}^n \bigl( x_k - x_j \bigr) \right) = \prod_{0 \leq j \lt k \leq n} \bigl( x_k - x_j \bigr).
\]
Hence, the last product is the value of the determinant given in the theorem. This completes the proof.
Theorem 2.
Let $n\in \mathbb{N}$ and let $\mathbb{P}_n$ be the vector space of all polynomials with real coefficients which are of degree less or equal $n$. The monomials $1, x, \ldots, x^n$ form a basis for $\mathbb{P}_n$.
Proof.
By the definition of a polynomial of degree less or equal $n$ we have
\[
\mathbb{P}_n = \operatorname{Span} \bigl\{ a_0 + a_1 x + \cdots + a_n x^n \, : \, a_k \in \mathbb{R} \ \forall k \in \{0,1,\ldots,n\} \bigr\}.
\]
To prove $1, x, \ldots, x^n$ form a basis for $\mathbb{P}_n$ we need to prove that they are linearly independent. To prove the linear independence we need to prove the following implication: For all $\alpha_0, \alpha_1,\ldots, \alpha_n \in \mathbb{R}$ we have
\[
\alpha_0 + \alpha_1 x + \cdots + \alpha_n x^n = 0 \ \ \forall x \in \mathbb{R}
\quad \Rightarrow \quad
\alpha_k = 0 \ \ \forall k \in \{0,1,\ldots,n\}.
\]
To prove this implication assume
\begin{equation} \label{eq:a1}\tag{1}
\bbox[5px, #88FF88, border: 1pt solid green]{
\alpha_0 + \alpha_1 x + \cdots + \alpha_n x^n = 0 \quad \forall x \in \mathbb{R}
}.
\end{equation}
The objective is to prove
\begin{equation} \label{eq:claim}\tag{2}
\bbox[5px, #FF4444, border: 1pt solid red]{
\alpha_k = 0 \quad \forall k \in \{0,1,\ldots,n\}
}.
\end{equation}
Let $x_0, x_1, \ldots, x_n$ be distinct real numbers. That is we assume that
\begin{equation} \label{eq:a2}\tag{3}
\bbox[5px, #88FF88, border: 1pt solid green]{
\prod_{0\leq j \lt k \leq n}\bigl(x_k - x_j\bigr) \neq 0
}.
\end{equation}
Since the assumption $\eqref{eq:a1}$ holds for all $x \in \mathbb{R}$ we have that
\begin{equation} \label{eq:e4}\tag{4}
\bbox[5px, #88FF88, border: 1pt solid green]{
\alpha_0 \cdot 1 + \alpha_1 x_k + \cdots + \alpha_n x_k^n = 0 \quad \forall k \in \{0,1,\ldots,n\}
}.
\end{equation}
In $\eqref{eq:e4}$ we have $n+1$ linear equations with $n+1$ unknowns $\alpha_0, \alpha_1, \ldots ,\alpha_n.$ This system can be written in matrix form as follows
\begin{equation}\label{eq:e5}\tag{5}
\bbox[5px, #88FF88, border: 1pt solid green]{
\left[ \begin{array}{ccccc}
1 & x_0 & \cdots & x_0^{n-1} & x_0^n \\
1 & x_1 & \cdots & x_1^{n-1} & x_1^n \\
\vdots & \vdots & \ddots & \vdots & \vdots \\
1 & x_{n-1} & \cdots & x_{n-1}^{n-1} & x_{n-1}^n \\
1 & x_n & \cdots & x_n^{n-1} & x_n^n
\end{array} \right] \left[ \begin{array}{c}
\alpha_0 \\[2pt] \alpha_1 \\[2pt] \vdots \\[2pt] \alpha_{n-1}\\[2pt] \alpha_n
\end{array} \right] = \left[ \begin{array}{c}
0 \\[2pt] 0 \\[2pt] \vdots \\[2pt] 0 \\[2pt] 0
\end{array} \right] }.
\end{equation}
In $\eqref{eq:e5}$ we have a homogeneous matrix equation with the Vandermonde matrix. In Theorem 1 we proved that the determinant of the Vandermonde matrix equals the expression in $\eqref{eq:a2}$ for which we assume that it is not zero. Therefore the matrix in $\eqref{eq:e5}$ is invertible. Consequently, equation $\eqref{eq:e5}$ implies that
\begin{equation*}
\bbox[5px, #88FF88, border: 1pt solid green]{
\left[ \begin{array}{c}
\alpha_0 \\[2pt] \alpha_1 \\[2pt] \vdots \\[2pt] \alpha_{n-1}\\[2pt] \alpha_n
\end{array} \right] = \left[ \begin{array}{c}
0 \\[2pt] 0 \\[2pt] \vdots \\[2pt] 0 \\[2pt] 0
\end{array} \right] }.
\end{equation*}
The preceding vector equality can be rewritten as
\begin{equation*}
\bbox[5px, #88FF88, border: 1pt solid green]{
\alpha_k = 0 \quad \forall k \in \{0,1,\ldots,n\}
}.
\end{equation*}
Thus, the claim in $\eqref{eq:claim}$ has been greenified, that is it has been proved. Since by the definition of polynomials of degree less or equal to $n$ we have
\begin{equation*}
\bbox[5px, #88FF88, border: 1pt solid green]{
\mathbb{P}_n = \operatorname{Span} \bigl\{ 1, x, \ldots, x^n\bigr\}
}
\end{equation*}
we have proved that $\bigl\{ 1, x, \ldots, x^n\bigr\}$ is a basis for $\mathbb{P}_n.$
This completes the proof.