On the induction argument of the "many paths to a basis" theorem I'm trying to make practical sense of the induction argument of the following famous theorem on the dimension of a finite-dimensional vector space.
Theorem
Let $n$ be a positive integer. If $V$ is a vector space containing two lists of vectors $x_1,\ldots,x_n$ and $y_1,\ldots,y_n$ of the same length $n$, such that
(1) $x_1,\ldots,x_n$ generate $V$, and
(2) $y_1,\ldots,y_n$ are independent,
then both lists are bases of $V$.
Update: For your convenience I've updated the post adding the full proof.
In the proof below, $\theta$ denotes the zero vector of $V$.
Proof. We have to show that list (1) is independent and list (2) is generating. The proof is by induction on $n$. Let $F$ be the field of scalars.
Suppose $n=1$. By assumption, $V = Fx_1$ and $y_1\neq \theta$. Say $y_1 = c x_1$. Since $y_1$ is nonzero, both $c$ and $x_1$ are non zero. From $x_1\neq\theta$ we see that the list $x_1$ is independent. Since every vector is a multiple of $x_1 = c^{-1}y_1$, and therefore of $y_1$ the list $y_1$ is generating.
Let $n\geq 2$ and assume that the statement in the theorem is true for lists of length $n-1$.
We assert first that $x_1,\ldots,x_n$ are independent. Assume to the contrary that this list is linearly dependent, i.e. one of the $x_i$ is a linear combination of the others. Suppose, for illustration, that $x_n$ is a linear combination  of $x_1,\ldots,x_{n-1}$. It follows that the list $x_1,\ldots,x_{n-1}$ generates $V$; for, its linear span includes $x_n$ as well as $x_1,\ldots,x_{n-1}$, so it must be all of $V$ by (1). Since the list $y_1,\ldots,y_{n-1}$ is independent by (2), it follows from the induction hypothesis that $y_1,\ldots,y_{n-1}$ generate $V$. In particular, $y_n$ is a linear combination of $y_1,\ldots, y_{n-1}$, contradicting (2). The contradiction shows that $x_1,\ldots,x_{n}$ is independent, as asserted.
The proof that $y_1,\ldots, y_n$ are generating will be accomplished by invoking the induction hypothesis in a suitable quotient space $V/M$; the first step is to construct an appropriate linear subspace $M$. Express $y_n$ as a linear combination of $x_1,\ldots,x_n$, say
$$
y_n = c_1x_1+\cdots+c_nx_n.
$$
Since $y_n\neq \theta$, one of the coefficients $c_i$ must be nonzero; rearranging the $x_i$, we can suppose that $c_n\neq 0$. It follows that
$$
x_n = (-c_1/c_n)x_1+\cdots+(-c_{n-1}/c_n)x_{n-1}+(1/c_n)y_n,
$$
thus the linear span of the list $x_1,\ldots,x_{n-1},y_n$ includes all of the vectors $x_1,\ldots,x_n$; in view of (1) we conclude that
$$
(*)\,\,\,\, x_1,\ldots,x_{n-1},y_n\,\,\text{generate } V.
$$
Let $M = Fy_n$ and let $Q:V\to V/M$ be the quotient mapping. Then
$$
(3)\,\,\,\ Qx_1,\ldots,Qx_{n-1}\text{ generate } V/M
$$
(by (*)) and
$$
(4)\,\,\,\ Qy_1,\ldots,Qy_{n-1}\text{ are independent}
$$
(by (2)), so by the induction hypothesis, both the lists (3) and (4) are bases of $V/M$. In particular, the list (4) is generating for $V/M$; since $M$ is generated by $y_n$, it follows (from another result not shown here) that $y_1,\ldots,y_n$ generate $V$.
Q.E.D.
I'm stuck at the induction step (in bold). I do understand that the assumption is a necessary logical step which is given for truth without questioning, in order to show that what follows is true.
My question is:
if $V$ has basis $x_1,\ldots,x_{n-1}$, how can it also have (a larger) basis $x_{1},\ldots,x_{n}$?
 A: It's not really clear from the statement of the theorem which sentence is proved by induction, I agree.
Consider this one: let $n \in \mathbb{N}$. Let us denote by $P_n$ the sentence:
for all vector space $V$, for all $n$-tuples $(x_1,\cdots,x_n)$ and $(y_1,\cdots,y_n)$ of vectors in $V$ such that the $x_i$'s generate $V$ and the $y_j$'s are linearly independent, then both are bases of $V$.
Now, let $V$ be a vector space, and $n \in \mathbb{N}$. Let us denote by $Q_n$ the sentence: for all $n$-tuples $(x_1,\cdots,x_n)$ and $(y_1,\cdots,y_n)$ of vectors in $V$ such that the $x_i$'s generate $V$ and the $y_j$'s are linearly independent, then both are bases.
Then $\forall n\in \mathbb{N},\ P_n$ can certainly be proved by induction, following the proof of your book, perhaps by making some things a bit more precise. The assertion $\forall n\in \mathbb{N},\ Q_n$ is also true, but for other reasons. Indeed, if $\dim V = n$ then $Q_n$ is a particular case of $P_n$, so is true. However, if $\dim V \neq n$, then $Q_n$ is of the form $\forall x \in \emptyset,\ blahblah$ which is obviously true and is not relevant to vector spaces.
A: 
if $V$ has basis $x_1,\ldots,x_{n-1}$, how can it also have (a larger) basis $x_{1},\ldots,x_{n}$

The $V$s aren't the same in each step. You should take $V'$ to be a subset of $V$, and take $x_1,\ldots,x_{n-1}$ and $y_1,\ldots,y_{n-1}$ to both be lists of vectors within $V'$, where $x_1,\ldots,x_{n-1}$ generate $V'$, and $y_1,\ldots,y_{n-1}$ are independent, and both are bases of $V'$ (this is a weaker version of the induction hypothesis, as the induction speaks of all possible lists of size $n-1$, not just for a particular subset of $V$). Then augment each by arbitrary $x_{n}$ and $y_{n}$, respectively, with $x_1,\ldots,x_{n}$ generating $V$, and $y_1,\ldots,y_{n}$ independent, and prove that these augmented lists are both bases of $V$.
