HMMT-Feb 2014 alg, Problem 10

For an integer $n$, let $f_{9}(n)$ denote the number of positive integers $d \leq 9$ dividing $n$. Suppose that $m$ is a positive integer and $b_{1}, b_{2}, \ldots, b_{m}$ are real numbers such that $f_{9}(n)=\sum_{j=1}^{m} b_{j} f_{9}(n-j)$ for all $n>m$. Find the smallest possible value of $m$.

Solution: 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}\left(n+M\right.$ !) 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 sth 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-$ $\left.\omega^{-1} z\right)=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$. Comment: Only at the beginning do we treat $F(x)$ strictly as a formal power series; later once we get the rational function representation $\sum_{d=1}^{6} \frac{x^{d}}{1-x^{d}}$, we can work with polynomial identities in general and don't have to worry about convergence issues for $|x| \geq 1$. $\fbox{28}$.

Answer: 28