How many matrices in $M_n(\mathbb{F}_q)$ are nilpotent? I have strong computational evidence to think that the answer is $q^{n(n-1)}$, although a proof eludes me.  Any ideas?
 A: There is a nice proof based on the two following lemmas. Let $V$ be a vector space of dimension $n$.

Lemma 1 (Fitting). For all $u \in \mathcal{L}(V)$, there exists a unique decomposition $V=W_N \oplus W_I$ such that :
  
  
*
  
*$u(W_N) \subset W_N$ and $u_{|_{W_N}}$ is nilpotent,   
  
*$u(W_I) \subset W_I$ and $u_{|_{W_I}}$ is inversible.
  

Sketch of proof. This a very special case of the Jordan normal form theorem.

Lemma 2. For all $k \leq n$ there is a one-to-one correspondence between  the decompositions $W_1 \oplus W_2$ of $V$ with $\dim W_1=n-\dim W_2 = k$ and the quotient $$GL(n)/(GL(k)\times GL(n-k)).$$

Sketch of proof. Consider the natural group action of $GL(n)$ on the set of such decompositions.

Let $N_k$ denote the number of nilpotent matrices in $M_k(\Bbb F_q)$. Using the two lemmas, we see that
$$
q^{n^2} = \#M_n(\Bbb F_q) = \sum_{k=0}^n (N_k\cdot\#GL_{n-k})\cdot\dfrac{\#GL_n}{\#GL_k\cdot \#GL_{n-k}} = \#GL_n\sum_{k=0}^n \frac{N_k}{\#GL_k}
$$
which yields for all $n \geq 2$,
$$\dfrac{N_n}{\#GL_n(\Bbb F_q)} = \dfrac{q^{n^2}}{\#GL_n(\Bbb F_q)} - \dfrac{q^{(n-1)^2}}{\#GL_{n-1}(\Bbb F_q)}.$$
The result follows after simplification using the well-known fact that $$\#GL_k(\Bbb F_q) = (q^k-1)(q^k-q)\dots(q^k-q^{k-1}).$$
