Please, how can I prove this elementary linear algebra theorem? 
I'm trying to prove it by induction, i.e, I know how to prove that it is true for k = 1, but then I get counfused because the next induction step would be :
Assume that it is true for k-1 ( where k-1 is the cardinality of S ) and then show it is true for k. I can't do this last part.
I would like to do it without using concepts such as dimesion an so on, since it is a very elementary theorem that preceeds these concepts ( on my book. ) Thank you !
 A: Presumably, you've seen the basic theory of solutions of systems of $m$ equations in $n$ unknowns, possibly in the form of the some theorems about matrices in relation to Gauss elimination. So, take $k+1$ vectors in $S$, say $y_1,\dots, y_{n+1}$. Write each as a linear combination of the vectors $x_1,\dots, x_n$ (by the way, it is not important that these vectors are linearly independent, the result and this suggested proof remain the same without that assumption). Consider the matrix of coefficients and think of it as representing a system of equations. How many equations does it represent? How many unknowns? Now, if the vectors you chose in $S$ were linearly independent, what does that mean about the space of solutions of the system? Which elementary theorem does it this contradict?
A: Try a proof by contradiction. Let $\{v_1,\dots.v_{k + 1}\} \in L(S)$ be independent. We know that $\{v_1,x_1,\dots,x_k\}$ is dependent. So there is some $j$ such that $x_j$ can be expressed as a linear combination of $\{v_1,x_1,\dots,x_{j - 1},x_{j + 1},\dots,x_k\}$. So if we remove $x_j$, $\{v_1,x_1,\dots,x_{j - 1},x_{j + 1},\dots,x_k\}$ is still a spanning set. Verify that we can add $v_2$ to the set, pick another value of $j$, and remove $x_j$ while still having the set be spanning, and so on until we have replaced all the $x$'s with $v$'s. Then we have that $\{v_1,\dots,v_k\}$ are spanning which yields a contradiction since $v_{k + 1}$ is independent to those vectors.
A: Use induction. For $k=1$ it's easy. Say $k\ge 2$. Assume the result true for $k-1$. Let $y_1$, $\ldots$, $y_{k+1}$ dependent on $x_1$, $\ldots$, $x_k$. If in the expressions for the $y_i$ the vector $x_k$ does not appear then the $y_i$'s are dependent on $k-1$ vectors, so linearly dependent. Otherwise, say $x_k$ appears in the linear expression for the $y_{k+1}$. In this case, from any other vector $y_i$, $1\le i \le k$ we can subtract a multiple of $y_{k+1}$ so the resulting vector
$$y'_i \colon = y_i - c_i y_{k+1}$$is dependent only on $x_1$, $\ldots$, $x_{k-1}$. Now by the induction hypothesis, the $k$ vectors $y'_i$ $1\le i \le k$ are linearly dependent
$$\sum_{i=1}^k a_i ( y_i - c_i y_{k+1}) = 0$$ ( where nor all $a_i$'s are $0$ ), and from here we get a linear dependence for $y_1$, $\ldots$, $y_{k+1}$.
A: orangeskid's proof is constructive and gives rise to a recursive algorithm. Per my comment, I'll start with a base case of $n = 0$. Furthermore, the condition that $S$ be independent is unnecessary. The result also holds if $S$ is a dependent set. As a constructive proof, the algorithm constructively witnesses the fact that the $n+1$ vectors are dependent. That is, it produces the  coefficients (not all $0$) that lead to a linear combination equal to $0$.  I'll write $\langle x_1,\dots, x_n \rangle$ for a finite sequence.
The algorithm will be represented by a function $\mathcal{D}$ which will take a sequence of vectors, $\langle v_1, \dots, v_n \rangle$ representing $S$, a sequence of vectors, $\langle w_1, \dots, w_{n+1} \rangle$, and produce a sequence of scalars, $\langle c_1, \dots, c_{n+1} \rangle$ such that $\sum_{i=1}^{n+1} c_i w_i = 0$. Since $w_i \in L(\{v_1,\dots,v_n\})$, $w_i = \sum_{j=1}^n a_j v_j$ and so we'll represent $w_i$ as $\langle a_{i,1},\dots,a_{i,n}\rangle$, which makes $\langle w_1, \dots, w_{n+1} \rangle$ a sequence of sequences, better known as a matrix.
When $n = 0$, then $S = \{\}$ and $L(S) = \{0\}$. This gives the base case of the algorithm:
$$\mathcal{D}(\langle\rangle,\langle\langle\rangle\rangle) \equiv \langle1\rangle$$
In the $n = m+1$ case, following orangeskid's proof we check whether $v_n$ occurs in any of the $w_i$. That is, if there is an $i$ such that $a_{i,n} \neq 0$. If there isn't, we can drop the last element of the sequences representing $w_i$ and take the first (or any) $n = m+1$ (out of $n+1$) $w_i$ and recurse:
$$\mathcal{D}(\langle v_1, \dots, v_n\rangle, \langle w_1,\dots, w_{n+1}\rangle) \equiv \langle c_1,\dots,c_n,0\rangle\text{ if }\forall i.a_{i,n}=0 \\
\text{where } w_i' = \langle a_1,\dots,a_m\rangle\text{ and }\langle c_1,\dots,c_n\rangle = \mathcal{D}(\langle v_1,\dots,v_m\rangle,\langle w_1',\dots,w_{m+1}'\rangle$$ 
Otherwise, if $a_{k,n} \neq 0$, we can write $w_i' = w_i - p_i w_k$ for $i \neq k$ such that $w_i' = \sum_{j=1}^m b_{i,j} v_j$. To accomplish this, we need to solve $a_{i,n} = p_i a_{k,n}$ which is just $p_i = \frac{a_{i,n}}{a_{k,n}}$. Generally, we have $b_{i,j} = a_{i,j} - p_i a_{k,j} = a_{i,j} - \frac{a_{i,n}a_{k,j}}{a_{k,n}}$. We now have $m+1$ vectors $w_i'$ each of length $m$, so we can recurse. The result is $\langle c_1, \dots, c_n\rangle$ such that $$\sum_{j=1}^{k-1} c_j w_j' + \sum_{j=k}^{n}c_j w_{j+1}' = 0 = \sum_{j=1}^{k-1} c_j (w_j - p_j w_k) + \sum_{j=k}^{n}c_j(w_{j+1}-p_{j+1}w_k)$$ Distributing gives the resulting coefficients $\langle c_1,\dots,c_{k-1},-\sum_{j=1}^{k-1} c_j p_j-\sum_{j=k}^nc_jp_{j+1},c_{k},\dots,c_{n}\rangle$. 
$$\mathcal{D}(\langle v_1, \dots, v_n\rangle, \langle w_1,\dots, w_{n+1}\rangle) \equiv \langle c_1,\dots,c_{k-1},-r,c_{k},\dots,c_n\rangle\text{ if }a_{k,n}\neq0 \\ \text{where }p_i = a_{i,n}/a_{k,n},\ w_i' = w_i - p_i w_n, \\
\langle c_1,\dots,c_n\rangle = \mathcal{D}(\langle v_1,\dots,v_{k-1},v_{k+1},\dots,v_n\rangle,\langle w_1',\dots,w_{k-1}',w_{k+1}',\dots,w_{n+1}'\rangle), \\ \text{and } r = \sum_{j=1}^{k-1} c_j p_j + \sum_{j=k}^{n}c_j p_{j+1}$$
You may notice that $\mathcal{D}$ is closely related to Gaussian elimination.
A: We'll use the following lemma, which can be shown by induction (try it next!):

Lemma. Let $V$ be a vector space, let $G_1 = \{v_1, \dots, v_n\}$ generate $V$, and let $L = \{w_1, \dots, w_m \} \subset V$ be independent. Then there exists a set $H \subseteq G_1$ containing $m$ distinct vectors such that
  $$G_2 := (G_1 \setminus H) \cup L $$
  still generates $V$.

This means that you can remove $m$ vectors from a generating system containing $n$ vectors, substitute them with $m$ with linearly independent vectors, and still obtain a generating system. Of course, since the statement has $H \subseteq G_1$, it must be that $m \leq n$, that is, $|H| = |L| \leq |G_1| = |G_2|$.
Now let us consider $L(S)$, which is a vector space generated by $S$. Let $S' = \{y_1, \dots, y_{k+1}\} \subset L(S)$: then $S'$ too trivially generates  $L(S)$ (just write some arbitrary $v \in L(S)$ as a linear combination of the $y_j$'s, then express each $y_j$ as a linear combination of $x_i$'s).
Let's prove your theorem by contradiction. Suppose that $S'$ is independent. Now apply the Lemma, using $S$ as $G_1$ and $S'$ as $L$. This implies that $|S'| \leq |S|$, that is, $k +1 \leq  k$, which is false for all integer $k$.
