Help with proving this three part theorem left to reader to prove by Halmos 
Every set of $n+1$ vectors in an $n$-dimensional vector space $V$ is linearly dependent. A set of $n$ vectors in $V$ is a basis if and only if it is linearly independent, or, alternatively, if and only if every vector in $V$ is a linear combination of elements of the set. (Paul R. Halmos, Finite-Dimensional Vector Spaces, 2e, section 8, theorem 2, page 14)

 A: Refering to Paul R. Halmos, Finite-Dimensional Vector Spaces, 2e:
Theorem 2 in section 8, page 14:
First part

Every set of $n + 1$ vectors in an $n$-dimensional vector space is
  linearly dependent.

Theorem 1 in the same section states:

The number of elements in any basis of a finite-dimensional vector
  space $\mathcal{V}$ is the same as in any other basis.

If there is a set of $n$ linearly independent vectors, taken from the set of $n +1$ linearly dependent vectors, they form a basis. This is a consequence of the theorem in section 7:

If $\mathcal{V}$ is a finite-dimensional vector space and 
  $\{y_1, ..., y_m\}$ is any set of linearly independent vectors in $\mathcal{V}$,
  then, unless the $y$'s already form a basis, we can find vectors
  $y_{m+1}, ..., y_{m+p}$ so that the totality of the $y$'s, that is,
  $\{y_1, ..., y_m, y_{m+1}, ..., y_{m+p}\}$, is a basis. In other
  words, every linearly independent set can be extended to a basis.

Since every linearly independent set can be extended to a basis, so can the set of $n$ linearly independent vectors chosen from the set of $n + 1$ vectors. But since every basis has $n$ elements, it already is one.
Now that it is shown that every set of $n$ linearly independent vectors is a basis, every vector in the vector space can be expressed as a linear combination of the $n$ linearly independent vectors chosen from the set of $n + 1$ vectors. Hence, if you add an arbitrary vector to the set of $n$ linearly independent vectors, it will be a linear combination of the other ones. But then, according to the theorem in section 6, the set is linearly dependent:

The set of non-zero vectors $x_1, ..., x_n$ is linearly dependent if
  and only if some $x_k$, $2 \le k \le n$, is a linear combination of
  the preceding ones.

If, on the other hand, you cannot find $n$ linearly independent vectors from the given set of $n + 1$ vectors, then the whole set is linearly dependent. Since every set containing a linearly dependent subset is itself linearly dependent.

Second part

A set of $n$ vectors in $\mathcal{V}$ is a basis if and only if it is
  linearly independent.

"$\Rightarrow$": From the definition of a basis (section 7, page 10) the constituting vectors have to be linearly independent:

A (linear) basis (or a coordinate system) in a vector space
  $\mathcal{V}$ is a set $\mathcal{X}$ of linearly independent vectors
  such that every vector in $\mathcal{V}$ is a linear combination of
  elements of $\mathcal{X}$.

"$\Leftarrow$": Using the same argument as in the first part, if there is a set of linearly independent vectors with the same number of elements than a basis of the vector space, then it is a basis, since every set of linearly independent vectors can be extended to a basis.

Third part

A set of $n$ vectors in $\mathcal{V}$ is a basis if and only if every
  vector in $\mathcal{V}$ is a linear combination of elements of the
  set.

"$\Rightarrow$": From the definition of a basis (see above) every vector of the vector space is a linear combination of the basis' elements.
"$\Leftarrow$": Assume there is a set of $n$ vectors such that every vector in the vector space is a linear combination of those. Assume also that these vectors do not form a basis. If they don't, they are linearly dependent (from the definition of a basis). As a consequence, the maximum number of linearly independent vectors in this set is $n-1$. From the theorem in section 7 (see above), every linearly independent set can be extended to a basis. But regardless which vector is added to the set, it is a linear combination of the remaining elements in the set. Hence, the set is linearly dependent and there is a linearly independent set which cannot be extended to a basis. A contradiction. To make the implication true, we might negate the premise:
For all sets of vectors such that every vector in the vector space is a linear combination of those we have that they form a basis.
