Proof that $\dim(U_1+U_2) = \dim U_1 + \dim U_2 - \dim(U_1\cap U_2)$ Lemma 1: If the subspace $U_1$ is spanned by $L$ and $U_2$ by $H$ then $\text{span}(L\cup H) = U_1 + U_2$ 
Linear Independence Lemma: If $(v_1,...,v_m)$ is linearly dependent in V then there exists $j \in \{2,...m\}$ such that:
a. $v_j \in \text{span}(v_1,...,v_{j-1})$
b. If the j-th term is removed from $(v_1,...,v_m)$ the span of the remaining list equals $\text{span}(v_1,...,v_m)$.
Proof of Theorem: For two subspaces $U$ and $W$ spanned by $(u_1,...,u_m)$ and $(w_1,...,w_n)$ respectively we have (by lemma 1) that $U+W$ is is spanned by $S=(u_1,...,u_m,w_1,...,w_n)$. 
Assume that S is linearly independent. Then $U \cap W = 0$ and  $\dim(U+W) = m+n = \dim(U) + \dim(W)$ so the identity holds.
Assume that S is linearly dependent. By the linear dependence lemma, there is a $w_i$ in S such that we can remove $w_i$ from S and we will still span $U+W$. We can continue this process until S is linearly independent and therefore a basis of $U+W$. Let $b$ be the number of elements that we removed from S. We have $\dim (U+W) = m+n-b$. By the linear independence lemma, every element we removed from S could be written as a linear combination of other elements in S, therefore each element we removed from S would have to be included in $U\cap W$. So $\dim(U\cap W)=b$ So the identity reduces to $m+n-b=m+n-b$. Q.E.D
This is a theorem in my textbook that the author took a different approach to prove. I'm worried about how true the claim "By the linear independence lemma, every element we removed from S could be written as a linear combination of other elements in S, therefore each element we removed from S would have to be included in $U\cap W$." is and the validity of lemma 1. If anyone could confirm my proof or find the flaw that would be great. Thank you.
 A: This a simple proof of the equality:
Let $\Phi: U_1\times U_2\to U_1+U_2,\; (u_1,u_2)\mapsto u_1+u_2$. Then $\Phi$ is a linear transformation and $\operatorname{Im}\Phi=U_1+U_2$ and $\ker \Phi$ is isomorphic to $U_1\cap U_2$. Hence the rank-nullity theorem applied to $\Phi$ gives the desired equality.
A: The statement that each element we removed from $S$ is an element of $U \cap W$ is false. For example, let $L = \{u_1 = (1,0,0), u_2 = (1,0,1)\}$ and $H = \{w_1 = (0,1,1), w_2=(0,1,-1)\}$. Here $L\cup H$ spans the whole space $R^3$, $U \cap W $ is the space generated by $e_3 = (0,0,1)$, but its basis is not part of $L \cup H$.
A: Instead of complicating the argument using induction, you may argue as follows: let $ \mathcal B $ be a basis of $ U_1 \cap U_2 $. Extend $ \mathcal B $ to bases $ \mathcal B_1 $ and $ \mathcal B_2 $ of $ U_1 $ and $ U_2 $, respectively. Then, by the inclusion-exclusion principle, we have 
$$ | \mathcal B_1 \cup \mathcal B_2 | = |\mathcal B_1| + |\mathcal B_2| - |\mathcal B_1 \cap \mathcal B_2| $$
where the horizontal bars denote set cardinality. I claim that $ \mathcal B = \mathcal B_1 \cap \mathcal B_2 $. Indeed, the inclusion $ \mathcal B \subseteq \mathcal B_1 \cap \mathcal B_2 $ is obvious from construction. The reverse inclusion follows since $ \mathcal B_1 \cap \mathcal B_2 $ is linearly independent, therefore its cardinality is at most $ |\mathcal B| $. Showing that $ \mathcal B_1 \cup \mathcal B_2 $ is linearly independent is left as an exercise. Now, translating this equality into dimensions gives
$$ \dim(U_1 + U_2) = \dim(U_1) + \dim(U_2) - \dim(U_1 \cap U_2) $$
which was to be shown.
