A simple approach is to overdo it a little and show that $n$-qubit Pauli operators form an orthogonal basis in a real vector space $L_H(\mathbb{C}^{2^n})$ of $n$-qubit Hermitian operators with appropriately defined inner product. To that end, we first show that $\langle A,B\rangle_{HS}:=\mathrm{tr}(A^\dagger B)$ defines an inner product$^1$. Next, we show that for any two Pauli operators $W:=W_1\otimes\dots\otimes W_n$ and $W':=W'_1\otimes\dots\otimes W'_n$ we have $\langle W,W'\rangle_{HS}=0$ if and only if $W\ne W'$. This implies$^2$ linear independence. Now, there are exactly $4^n$ Pauli operators in $L_H(\mathbb{C}^{2^n})$. However$^3$, $\dim L_H(\mathbb{C}^k)=k^2$, so Pauli operators span $L_H(\mathbb{C}^{2^n})$.

^{$^1$ The function $\langle .,.\rangle_{HS}$ is known as the Hilbert-Schmidt inner product.
$^2$ Because the coefficient in front of $W_k$ in a linear combination $A$ is proportional to $\langle W_k,A\rangle_{HS}$.
$^3$ There is a linear bijection between $L_H(\mathbb{C}^k)$ and $\mathbb{R}^{k^2}$.}

A simple approach is to overdo it a little and show that $n$-qubit Pauli operators form an orthogonal basis in the real vector space $L_H(\mathbb{C}^{2^n})$ of $n$-qubit Hermitian operators with appropriately defined inner product. To that end, we first show that $\langle A,B\rangle_{HS}:=\mathrm{tr}(A^\dagger B)$ is an inner product$^1$. Next, we calculate that for any two Pauli operators $W=W_1\otimes\dots\otimes W_n$ and $W'=W'_1\otimes\dots\otimes W'_n$ we have $\langle W,W'\rangle_{HS}=0$ if and only if $W\ne W'$. This implies$^2$ linear independence. Finally, there is a linear bijection between $L_H(\mathbb{C}^k)$ and $\mathbb{R}^{k^2}$, so $\dim L_H(\mathbb{C}^k)=k^2$. But there are $4^n$ Pauli operators in $L_H(\mathbb{C}^{2^n})$, so they form a basis.

^{$^1$ The function $\langle .,.\rangle_{HS}$ is known as the Hilbert-Schmidt inner product.
$^2$ Because the coefficient in front of $W_k$ in a linear combination $A$ is proportional to $\langle W_k,A\rangle_{HS}$.}