If a subspace S is spanned by $n$ vectors, any subset of S with $m>n$ vectors is linearly dependent So I am in an introductory linear algebra(with proofs) class, and I came across the following theorem:
If $S$ is a subspace of a vector space $V(F)$ and is generated by $\{a_1,...,a_n\}$ then any subset $\{b_1,...,b_m\}$ of $S$ with $m>n$ is linearly dependent. 
The proof in the textbook is done through induction (as most proofs regarding finite sets are) but I really do not follow it and I feel there is a simpler way of doing it. A hint would be appreciated. 
 A: The way I see it, the statement is equivalent to the fact that a system of linear equations with more unknowns than the number of equations always has a solution.
Let $S$ be the subspace of $V(F)$ spanned by $a_{1}, a_{2}, \dots, a_{n}$ so that any member $v \in S$ can be expressed as $$v = c_{1}a_{1} + c_{2}a_{2} + \dots + c_{n}a_{n}$$ where $c_{i}$ are scalars in field $F$.
Now let $b_{1}, b_{2}, \dots, b_{m} \in S$ with $m > n$. Then we have scalars $c_{ij}$ such that $$b_{i} = c_{i1}a_{1} + c_{i2}a_{2} + \dots+ c_{in}a_{n}\tag{1}$$ for all $i = 1, 2,\dots, m$. Consider the equation $$d_{1}b_{1} + d_{2}b_{2} + \dots+d_{m}b_{m} = 0\tag{2}$$ for some scalars (yet to be found) $d_{i}$. It is now easy to see that the system of linear equations $$\sum_{i = 1}^{m}{c_{ij}}d_{i} = 0$$ for $j = 1, 2, \dots, n$ has a non-trivial solution $d_{i}$ (as $m > n$). From $(1)$ and $(2)$ it is now obvious that $b_{1}, b_{2}, \dots, b_{m}$ are linearly dependent.
A: This proof is probably based on the same idea as the one in your textbook, but hopefully it will give you another point of view on the critical argument.
Let's start off assuming that we have a generating set $A = \{a_1, \dots, a_n\}$ and a linearly independent set $B = \{b_1, \dots, b_m\}$ where $m \geq n$. We'll first show that we can replace any $b_i$ in $B$ with some $a_j$ without losing independence. We prove this by contradiction. Take $i \in \{1, \dots, m\}$ and make the assumption that we can't find a suitable $j$. This means that the set $\{a_j,b_1, \dots, b_m\} \setminus \{b_i\}$ is linearly dependent for each $j \in \{1, \dots, n\}$.
Since $B$ is linearly independent, $B \setminus \{b_i\}$ is also linearly independent, so this implies that each $a_j$ can be written as a linear combination of $b_1, \dots, b_{i-1}, b_{i+1}, \dots, b_m$. But now, since $b_i$ can be written as a linear combination of $a_1, \dots, a_n$, we can also write $b_i$ as a linear combination of $b_1, \dots, b_{j-1}, b_{j+1}, \dots, b_m$, which leads to the set $B$ being linearly dependent. Hence, the assumption that no suitable $j$ exists must be false.
Now that we have proved that we can replace any $b_i$ in $B$ with some element from $A$ without losing linear independence, we can do this for each $b_1, \dots, b_n$ and we end up with a linearly independent subset of $\{a_1, \dots, a_n, b_{n+1}, \dots, b_m\}$. If $n < m$, then this set clearly is not linearly independent. Hence, we must have $n = m$.
