, 2014

Solution:

Answer: $28$

Let $M=9$. Consider the generating function
$$F(x)=\sum_{n \geq 1} f_{M}(n) x^{n}=\sum_{d=1}^{M} \sum_{k \geq 1} x^{d k}=\sum_{d=1}^{M} \frac{x^{d}}{1-x^{d}}$$
Observe that $f_{M}(n)=f_{M}(n+M!)$ for all $n \geq 1$ (in fact, all $n \leq 0$ as well). Thus $f_{M}(n)$ satisfies a degree $m$ linear recurrence if and only if it eventually satisfies a degree $m$ linear recurrence. But the latter occurs if and only if $P(x) F(x)$ is a polynomial for some degree $m$ polynomial $P(x)$. (Why?)

Suppose $P(x) F(x)=Q(x)$ is a polynomial for some polynomial $P$ of degree $m$. We show that $x^{s}-1 \mid P(x)$ for $s=1,2, \ldots, M$, or equivalently that $P(\omega)=0$ for all primitive $s$th roots of unity $1 \leq s \leq M$. Fix a primitive $s$th root of unity $\omega$, and define a function
$$F_{\omega}(z)=\left(1-\omega^{-1} z\right) \sum_{s \nmid d \leq M} \frac{z^{d}}{1-z^{d}}+\sum_{s \mid d \leq M} \frac{z^{d}}{1+\left(\omega^{-1} z\right)+\cdots+\left(\omega^{-1} z\right)^{d-1}}$$
for all $z$ where all denominators are nonzero (in particular, this includes $z=\omega$).

Yet $F_{\omega}(z)-F(z)\left(1-\omega^{-1} z\right)=0$ for all complex $z$ such that $z^{1}, z^{2}, \ldots, z^{M} \neq 1$, so $P(z) F_{\omega}(z)-Q(z)(1-\omega^{-1} z)=0$ holds for all such $z$ as well. In particular, the rational function $P(x) F_{\omega}(x)-Q(x)\left(1-\omega^{-1} x\right)$ has infinitely many roots, so must be identically zero once we clear denominators. But no denominator vanishes at $x=\omega$, so we may plug in $x=\omega$ to the polynomial identity and then divide out by the original (nonzero) denominators to get $0=P(\omega) F_{\omega}(\omega)-Q(\omega)\left(1-\omega^{-1} \omega\right)=P(\omega) F_{\omega}(\omega)$. However,
$$F_{\omega}(\omega)=\sum_{s \mid d \leq M} \frac{\omega^{d}}{1+\left(\omega^{-1} \omega\right)+\cdots+\left(\omega^{-1} \omega\right)^{d-1}}=\sum_{s \mid d \leq M} \frac{1}{d}$$
is a positive integer multiple of $1/d$, and therefore nonzero. Thus $P(\omega)=0$, as desired.

Conversely, if $x^{s}-1 \mid P(x)$ for $s=1,2, \ldots, M$, then $P(x)$ will clearly suffice. So we just want the degree of the least common multiple of the $x^{s}-1$ for $s=1,2, \ldots, M$, or just the number of roots of unity of order at most $M$, which is $\sum_{s=1}^{M} \phi(s)=1+1+2+2+4+2+6+4+6=28$.