[proofplan] We proceed by induction on the deficit $n - k$. If $k = n$, the independent set already has the right cardinality and is therefore a basis by the [Dimension Count Criterion](/theorems/3272). If $k < n$, the independent set does not span $V$, so we can find a vector outside its span. Appending this vector preserves linear independence and increases the count by one, reducing the deficit. The inductive hypothesis completes the extension. [/proofplan]

[step:Base case: an independent set of size $n$ is already a basis] If $k = n$, then $\{u_1, \ldots, u_n\}$ is a linearly independent subset of $V$ with exactly $n = \dim V$ elements. By the [Dimension Count Criterion](/theorems/3272), a linearly independent subset of $V$ with $n$ elements is a basis for $V$. No additional vectors are needed. [/step]

[step:Show that a linearly independent set of size $k < n$ does not span $V$]Suppose $k < n$. We claim that $\operatorname{span}(u_1, \ldots, u_k) \neq V$. [claim:A spanning set of size $k < n$ contradicts $\dim V = n$] If $\operatorname{span}(u_1, \ldots, u_k) = V$, then by the [Extraction of Bases from Spanning Sets](/theorems/3271), some subset of $\{u_1, \ldots, u_k\}$ is a basis for $V$. Every basis for $V$ has exactly $n$ elements (by definition of dimension), but every subset of $\{u_1, \ldots, u_k\}$ has at most $k < n$ elements. This is a contradiction. [/claim] [proof] The [Extraction of Bases from Spanning Sets](/theorems/3271) guarantees that from any spanning set one can extract a basis. A basis has exactly $\dim V = n$ elements. Since $k < n$, no subset of a $k$-element set can have $n$ elements, giving the desired contradiction. [/proof][/step]

[guided]The next step will choose a vector outside $\operatorname{span}(u_1, \ldots, u_k)$, which requires this span to be a proper subspace of $V$. We verify this by contradiction. Suppose $\operatorname{span}(u_1, \ldots, u_k) = V$. Then $\{u_1, \ldots, u_k\}$ is a spanning set for $V$ with $k$ elements. By the [Extraction of Bases from Spanning Sets](/theorems/3271), some subset $B \subset \{u_1, \ldots, u_k\}$ forms a basis for $V$. Every basis for $V$ has exactly $\dim V = n$ elements, so $|B| = n$. But $B \subset \{u_1, \ldots, u_k\}$ implies $|B| \le k$, and $k < n$ by assumption. This gives $n = |B| \le k < n$, a contradiction. Therefore $\operatorname{span}(u_1, \ldots, u_k) \subsetneq V$, confirming that there must exist vectors in $V$ not expressible as linear combinations of $u_1, \ldots, u_k$.[/guided]

[step:Choose a vector outside the span and verify that appending it preserves independence]Since $\operatorname{span}(u_1, \ldots, u_k) \subsetneq V$, there exists $v_{k+1} \in V \setminus \operatorname{span}(u_1, \ldots, u_k)$. We show that $\{u_1, \ldots, u_k, v_{k+1}\}$ is linearly independent. Suppose \begin{align*} a_1 u_1 + \cdots + a_k u_k + a_{k+1} v_{k+1} = 0 \end{align*} for scalars $a_1, \ldots, a_k, a_{k+1}$. If $a_{k+1} \neq 0$, then \begin{align*} v_{k+1} = -\frac{a_1}{a_{k+1}} u_1 - \cdots - \frac{a_k}{a_{k+1}} u_k \in \operatorname{span}(u_1, \ldots, u_k), \end{align*} contradicting the choice of $v_{k+1} \notin \operatorname{span}(u_1, \ldots, u_k)$. Therefore $a_{k+1} = 0$, and the equation reduces to $a_1 u_1 + \cdots + a_k u_k = 0$. Since $\{u_1, \ldots, u_k\}$ is linearly independent, $a_1 = \cdots = a_k = 0$. Thus all coefficients vanish, confirming linear independence.[/step]

[guided]A vector chosen outside the span of an independent set cannot be written as a linear combination of those vectors, and this is precisely what prevents a nontrivial linear relation. Since $\operatorname{span}(u_1, \ldots, u_k) \subsetneq V$, there exists $v_{k+1} \in V \setminus \operatorname{span}(u_1, \ldots, u_k)$. We need to verify that $\{u_1, \ldots, u_k, v_{k+1}\}$ is linearly independent. Consider a linear combination \begin{align*} a_1 u_1 + \cdots + a_k u_k + a_{k+1} v_{k+1} = 0. \end{align*} We must show all $a_i = 0$. Examine $a_{k+1}$ first. If $a_{k+1} \neq 0$, we could solve for $v_{k+1}$: \begin{align*} v_{k+1} = -\frac{a_1}{a_{k+1}} u_1 - \cdots - \frac{a_k}{a_{k+1}} u_k, \end{align*} which would place $v_{k+1}$ in $\operatorname{span}(u_1, \ldots, u_k)$. But $v_{k+1}$ was chosen outside this span, so $a_{k+1} = 0$. The relation then becomes $a_1 u_1 + \cdots + a_k u_k = 0$, and the linear independence of $\{u_1, \ldots, u_k\}$ forces $a_1 = \cdots = a_k = 0$. So appending a vector from outside the span always preserves linear independence.[/guided]

[step:Complete the extension by induction on the deficit $n - k$]We proceed by induction on $n - k$, the number of vectors that must be appended. **Base case.** If $n - k = 0$, then $k = n$ and $\{u_1, \ldots, u_n\}$ is a basis by the first step. **Inductive step.** Suppose the result holds whenever the deficit is at most $n - k - 1$, and consider a linearly independent set $\{u_1, \ldots, u_k\}$ with $k < n$. By the preceding steps, $\{u_1, \ldots, u_k, v_{k+1}\}$ is a linearly independent subset of $V$ with $k + 1$ elements and deficit $n - (k+1) = n - k - 1$. By the inductive hypothesis, there exist $v_{k+2}, \ldots, v_n \in V$ such that \begin{align*} \{u_1, \ldots, u_k, v_{k+1}, v_{k+2}, \ldots, v_n\} \end{align*} is a basis for $V$. This completes the induction.[/step]

[guided]The induction formalises the intuition that we keep appending one vector at a time. At each stage, the independent set grows by one element and the deficit $n - k$ decreases by one. The process must terminate because the deficit is a non-negative integer that strictly decreases at each step. **Base case.** When the deficit $n - k = 0$, we have $k = n$ and the [Dimension Count Criterion](/theorems/3272) immediately gives us a basis. **Inductive step.** Assume the result holds for any linearly independent set whose deficit is at most $n - k - 1$. Given a linearly independent set $\{u_1, \ldots, u_k\}$ with $k < n$, we showed that there exists $v_{k+1} \in V \setminus \operatorname{span}(u_1, \ldots, u_k)$ such that $\{u_1, \ldots, u_k, v_{k+1}\}$ is linearly independent. This new set has $k + 1$ elements, so its deficit is $n - (k+1)$, which is at most $n - k - 1$. The inductive hypothesis applies, yielding vectors $v_{k+2}, \ldots, v_n$ that complete the extension to a basis \begin{align*} \{u_1, \ldots, u_k, v_{k+1}, v_{k+2}, \ldots, v_n\}. \end{align*} This closes the induction and establishes the theorem.[/guided]