This is an elaboration on Stanley's reference to Exercise 5.13 in EC2. In these two 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).