Skip to main content
3 of 3
replaced http://mathoverflow.net/ with https://mathoverflow.net/

There are related examples at this MO question, but most power series identities can be categorified to natural isomorphisms between combinatorial species, which are functors $\text{FinSet}_0 \to \text{FinSet}_0$ from the category of finite sets and bijections to itself. The idea is that the decategorification of a species $F$ is the power series $\sum F(n) \frac{x^n}{n!}$ where $F(n)$ is the cardinality of $F(S)$, where $|S| = n$.

Then $x$ is the decategorification of the species $X$ which corresponds to the structure of "being a one-element set." $L = \frac{1}{1-x}$ is the decategorification of the unique species satisfying $L \cong 1 + xL$, or "an $L$-structure is either empty or an $x$-structure together with an $L$-structure." (Addition and multiplication of generating functions correspond to natural operations on species which are left as an exercise to define.) Then the identity we want is $L \cong 1 + x + x^2 + ...$ which follows just by repeatedly substituting the isomorphism $L \cong 1 + xL$ into itself.

Alternately one can define $L$ to be the species of linear orders and then show that $L \cong 1 + xL$.

The finite case is similar. Of course one can go much further with these ideas; see, for example, Bergeron, Labelle, and Leroux. I am sure Todd Trimble will also have something interesting to say.

Qiaochu Yuan
  • 118.2k
  • 40
  • 447
  • 741