I cannot seem to figure out how to prove the following:
"Prove that if a vector space has dimension $n$ then any $n + 1$ of its vectors are linearly dependent."
I reckon applying proof by contradiction might be a useful approach, but cannot seem to figure it out. Maybe weak induction as well? How would one go about this?
Below Edit 1 - Made to accomodate question requesting further specification:
"Linearly independent": A set of vectors $\{a_1, a_2,a_3…,a_n\}$ is seen as being linearly independent if $x_1a_1 + x_2a_2 + x_3a_3 + x_na_n = 0 \space (null vector)$ only is satisfied for $x_1 = x_2 = x_3 = x_n = 0$, then the set $\{a_1, a_2,a_3…,a_n\}$ is linearly independent. (${x_1,x_2,x_3,…,x_n}$ are arbitrary scalars)
"Definition of dimension": Let $V$ be a vector space. The number of vectors in a basis for $V$ is called the dimension of $V$, and is written $ \dim V$.
Best Answer
For sake of contradiction, suppose there is a set of vectors $\{u_1, \ldots, u_{n+1}\}$ in an $n$-dimensional vector space $V$ such that $\{u_1, \ldots, u_{n+1}\}$ are linearly independent. Let $B = \{v_1, \ldots, v_n\}$ be a basis for $V$. Then $B$ spans $V$, and we can write
$$ u_1 = a_1v_1 + \cdots + a_nv_n $$
Since $\{u_1, \ldots, u_{n+1}\}$ is linearly independent, it follows that no $u_i$ can be zero. This implies that there is at least one $j$ such that $a_j \neq 0$. Without loss of generality, assume that $j = 1$. Then we may write
$$ \begin{aligned} v_1 & = \frac{1}{a_1}u_1 - \frac{a_2}{a_1}v_2 - \cdots - \frac{a_n}{a_1}v_n & (1) \end{aligned} $$
Now let $B_1 = \{u_1, v_2, \ldots, v_n\}$. Since $B$ spans $V$, we can write
$$ v = \lambda_1v_1 + \cdots + \lambda_nv_n $$
for any $v\in V$. By $(1)$, we have
$$ \begin{align} v & = \lambda_1(\frac{1}{a_1}u_1 - \frac{a_2}{a_1}v_2 - \cdots - \frac{a_n}{a_1}v_n) + \lambda_2v_2 + \cdots + \lambda_nv_n \\ & = \frac{\lambda_1}{a_1}u_1 + \frac{-\lambda_1 a_2}{a_1}v_2 + \lambda_2v_2 + \cdots + \frac{-\lambda_1 a_n}{a_1}v_n + \lambda_nv_n \\ & = \frac{\lambda_1}{a_1}u_1 + (\frac{-\lambda_1 a_2}{a_1} + \lambda_2)v_2 + \cdots + (\frac{-\lambda_1 a_n}{a_1} + \lambda_n)v_n \\ & = \lambda_1^{'}u_1 + \lambda_2^{'}v_2 + \cdots + \lambda_n^{'}v_n \\ \end{align} $$
Thus, we can write any $v \in V$ in terms of the elements of $B_1$, which means $B_1$ spans $V$.
Suppose we have obtained $B_{i - 1} = \{u_1,\ldots, u_{i-1},v_i,\ldots, v_n\}$ and have shown that it spans $V$. Then we may write
$$ u_i = a_1u_1 + \cdots + a_{i-1}u_{i-1} + a_iv_i + \cdots + a_nv_n $$
for some $a_1, \ldots, a_n \in \mathbb{R}$. Since $u_i$ is a non-zero vector, there must be a $k$ such that $a_k \neq 0$. Let $j$ be the largest index for which $a_j \neq 0$. This $j$ must satisfy $j \geq i$, for if $j < i$, then $a_i = a_{i+1} = \ldots = a_n = 0$, which implies that
$$ u_i = a_1u_1 + \cdots + a_{i-1}u_{i-1} $$
which contradicts that $\{u_1, \ldots, u_{n+1}\}$ is linearly independent. Without loss of generality, assume $j = i$. Then we can switch $u_i$ with $v_i$ in $B_{i-1}$ to obtain $B_i = \{u_1,\ldots, u_{i-1}, u_i,v_{i+1},\ldots, v_n\}$, which can be shown to span $V$ by a substitution similar to the one using $(1)$ above.
Continue to do this until the $n$th step, where $B_n = \{u_1, u_2, \ldots, u_n\}$. Previously, we showed that if $B_{i-1}$ spans $V$, then our operation of switching $u_i$ with $v_i$ to get $B_i$ also makes $B_i$ span $V$. Therefore, $B_n$ must span $V$ (by induction starting with $B_1$). Since $u_{n+1}$ is in $V$, and since $B_n$ spans $V$, we can write
$$ u_{n+1} = a_1u_1 + \cdots + a_nu_n $$
for some $a_1, \ldots, a_n \in \mathbb{R}$. But this contradicts that $\{u_1, \ldots, u_{n+1}\}$ is linearly independent. Therefore, it must not be the case that $\{u_1, \ldots, u_{n+1}\}$ is linearly independent, which is to say that $\{u_1, \ldots, u_{n+1}\}$ must be linearly dependent. $$\tag*{$\blacksquare$}$$