This is an elaboration on Stanley's reference to Exercise 5.13 in EC2. In <a href="https://qchu.wordpress.com/2015/11/04/the-categorical-exponential-formula/">these</a> <a href="https://qchu.wordpress.com/2015/11/25/conjugacy-classes-of-finite-index-subgroups/">two</a> blog posts you can find proofs using groupoid cardinality of the following results. For a finitely generated group $G$ let $s_n(G)$ denote the number of subgroups of index $n$ and let $c_n(G)$ denote the number of conjugacy classes of subgroups of index $n$.

> **Exercise 5.13a:** $$\sum_{n \ge 0} \frac{|\text{Hom}(G, S_n)|}{n!} z^n = \exp \left( \sum_{n \ge 1} s_n(G) \frac{z^n}{n} \right).$$ 

> **Exercise 5.13c:** $$\sum_{n \ge 0} \frac{|\text{Hom}(\mathbb{Z} \times G, S_n)|}{n!} z^n = \prod_{n \ge 1} \frac{1}{(1 - z^n)^{c_n(G)}}.$$

Taking logarithms on both sides of Theorem 2 and applying Theorem 1 gives

$$s_n(\mathbb{Z} \times G) = \sum_{d \mid n} d c_d(G)$$

which, when applied to $G = \mathbb{Z}^k$, gives the second recurrence in Carl-Fredrik's answer (which is essentially the content of Exercise 5.13d).