Prove that the space $S$ of the symmetric matrices $n \times n$ has dimension $n(n+1)/2$.
$\bf{Just\;an\;idea:}$
Use induction
For example: writte an arbitraty matrice $3 \times 3$ as
$\left(\begin{array}{ccc} a & b & c \\ b & d &e \\ c & e & f \end{array}\right) = a\left(\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 0 &0 \\ 0 & 0 & 0 \end{array}\right) + b\left(\begin{array}{ccc} 0 & 1 & 0 \\ 1 & 0 &0 \\ 0 & 0 & 0 \end{array}\right) + c\left(\begin{array}{ccc} 0 & 0 & 1 \\ 0 & 0 &0 \\ 1 & 0 & 0 \end{array}\right) + d\left(\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 1 &0 \\ 0 & 0 & 0 \end{array}\right) + e\left(\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 &1 \\ 0 & 1 & 0 \end{array}\right) + f\left(\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 &0 \\ 0 & 0 & 1 \end{array}\right)$.
We obtain a set with $6 = 3(3 + 1)/2$ matrices LI, then a basis for space
Use this fact in induction
This is just an idea. I want to know if it works.
$E_{i,j}+E_{j,i}$ are $\frac{n(n-1)}{2} + n$ symmetric linearly independent matrices (pick 2 different $i,j$ and $i=j$ in $n$ ways). $E_{i,j}-E_{j,i}$ are $\frac{n(n-1)}{2}$ antisymmetric linearly independent matrices (can't pick $i=j$ here). All of these are $n^2$ and of course all linearly independant cause $-A= A^T = A \implies A=0$.
Note that we are basically saying that the space of matrices can be splitted in symmetric + antisymmetric, and this sum is direct! (Remember that you can write every matrix $A = \frac{A+A^T}{2} + \frac{A-A^T}{2}$ where the first is of course symmetric and the second one antisymmetric. We also showed that a matrix can't be in the intersection of these 2 spaces cause a matrix can't be both symmetric and antisymmetric).