Let $V$ be a vector space over a field $k$ and $S = \oplus S_n$ the symmetric algebra on $V$. If $f$ is a $k$-endomorphism of $V$, then $f$ extends to a linear operator $f_n$ on $S_n$ for each $n$. What is the trace of $f$ on $S_n$? There’s a surprisingly elegant way to compute this, which encapsulates the combinatorics of computing $f_n$ directly into a formal power series, which I learnt from Bourbaki’s “Groupes et algebres de Lie”:

$$

\sum_{m=0}^\infty {\rm Tr}(f_n)T^n = \det(1 – fT)^{-1}

$$

The proof of this identity is not difficult. First, we may as well assume $k$ is algebraically closed since computing the trace does not depend on the conjugacy class of a matrix chosen for $f$. In this case we can choose a basis $v_1,\dots, v_k$ of $V$ such that $f$ is in lower-triangular form, with diagonal entries $\lambda_1,\dots,\lambda_k$.

Choose a basis of the symmetric algebra $S_n$ to be the vectors $v_1^{i(1)}\otimes\cdots\otimes v_k^{i(k)}$ with $\sum_j i(j) = n$, ordered lexicographically. Then the diagonal entries of $f_n$ will be the products $\lambda_1^{i(1)}\cdots\lambda_k^{i(k)}$ (this part requires a little thought), so

$$

{\rm Tr}(f_n) = \sum_{i(1) + \cdots + i(k) = n} \lambda_1^{i(1)}\cdots\lambda_k^{i(k)}

$$

Hence,

$$

\sum_{n=0}^\infty {\rm Tr}(f_n)T^n \\

= \sum_{n=0}^\infty\sum_{i(1) + \cdots + i(k)=n}\lambda_1^{i(1)}\cdots\lambda_k^{i(k)}T^n\\

=\sum_{n=0}^\infty \lambda_1^nT^n \cdots \sum_{n=0}^\infty \lambda_nT^n\\

=(1-\lambda_1T)^{-1}\cdots (1-\lambda_kT)^{-1}

=\det(1 – fT)^{-1}

$$

The key observation was that term $\lambda_1^{i(1)}\cdots\lambda_k^{i(k)}T^n$ for $i(1) + \cdots + i(k) = n$ corresponds to the way power series are multiplied. To give an example, consider the matrix

$$

\begin{pmatrix}1 & 2\\-1 & 4\end{pmatrix}

$$

on a $2$-dimensional vector space. Then $\det(1 – fT)$ is $(1- 2T)(1 – 3T)$. To compute its inverse we must find the following product of power series:

$$

(1 + 2T + 4T^2 + 8T^3 + \cdots)(1 + 3T + 9T^2 + 27T^3 + \cdots)

$$

For example, ${\rm Tr}(f_3) = 8 + 4\cdot 3 + 2\cdot 9 + 27 = 65$. In general,

$$

{\rm Tr}(f_k) = \sum_{j=0}^k 2^{k-j}3^j.

$$

Getting power series to keep track of this calculation really makes the calculation straightforward – for example,

$$

{\rm Tr}(f_{100}) = 1546132562196033990574082188840405015112916155251

$$