find the smallest possible value of m so that there are real numbers $b_j$ satisfying $f_9(n) = \sum_{j=1}^m b_j f_9(n-j)$ for $n>m$

Question

For an integer n, let $f_9(n)$ denote the number of positive integers $d\leq 9$ dividing n. Suppose $m$ is a positive integer and $b_1,b_2,\cdots, b_m$ are real numbers so 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.

Let $F(x) = \sum_{i=0}^\infty f_M(i) x^i$, where $M=9.$ Then $F(x) = \sum_{j=1}^M \sum_{k\ge 1} x^{jk} = \sum_{j=1}^M \dfrac{x^j}{1-x^j}.$ Now note that if $f_n$ is a sequence that satisfies a recurrence where $f_n = \sum_{j=1}^m b_j f_{n-j}$ for all $n>m$, some $m\ge 1$, and if $T(x) = \sum_{n\ge 0} f_n x^n,$ then we can find a polynomial $Q(x)$ so that $T(x)Q(x) =P(x)$ for some polynomial P of degree at most $m$. Indeed, let $Q(x) = \sum_{j=1}^m b_j x^{m+1-j}-1$. Then $T(x)Q(x) = \sum_{k=0}^\infty \sum_{j=0}^k t_j q_{k-j} x^k,$ where $t_j$ and $q_i$ are the coefficients of $x^j$ and $x^i$ in $T(x)$ and Q(x) respectively. For $k>m$, we have $\sum_{j=0}^k t_j q_{k-j} = -t_k+t_{k-1}b_m + \cdots + t_{k-m}b_1 = 0,$ so the only potentially nonzero coefficients of $T(x)Q(x)$ are the coefficients of $x^i$ for $i\leq m,$ which proves the claim.

But how do I proceed from here?

Answer 1

It seems to me that you have demonstrated enough knowledge to be able to work on the problem, but haven't quite been able to push through / apply it. Here is a solution using the start of your approach.

1. Consider the generating function $F(x) = \sum f_9 (i) x^i$.
2. (As OP stated, though without details) $F(x) = \sum_{j=1}^9 \frac{x^j}{1-x^j}$.
3. (OP claimed some version of this. Prove it.) If $ F(x) = \frac{P(x)}{Q(x) }$, where $ \gcd(P(x), Q(x) ) = 1$, then $f_9(n)$ can minimally be written as a linear recurrence of exactly $ \deg (Q)$ terms.
4. It remains to calculate $F(x)$ as a rational polynomial.

Honestly, at this point, depending on your goals, you could just calculate that rational polynomial, tedious as it may be (or verify with Wolfram). If you're looking to go deeper into the theory, work through the remaining steps

5. For example, it is clear that we could have $F(x) = \frac{p(x) } { \prod_{i=1}^9 (1-x^i) }$, so the answer is at most 45.
6. Can we do better than the product of all the denominators? Almost certainly. From the theory of partial fractions, just $(1-x)$ will be more than sufficient (it might cancel out). We don't need $(1-x)^9$ in $ \prod ( 1-x^i)$. Same with the other duplicate terms like $1+x, 1+x^2, 1-x+x^2, $ etc, so we should consider the cyclotomic polynomials $\Phi_n(x)$.
7. We can have $F(x) = \frac{p(x) }{ \prod_{i=1}^9 \Phi_n(x) }$. So, the answer is at most 28.
8. In fact, the answer is 28, because we need all of those cyclotomic polynomials. How can we demonstrate that? What does it mean to demonstrate it, what is the equation we need to prove?

We need to show that $ \Phi_k (x) \not \mid F(x)\prod_{i=1}^9 \Phi_n(x) $ for $ k = 1$ to 9.
If so, the gcd of numerator and denominator is 1, so we are done via point 3.

For another hint,

It might be easier to work with $F(x) = \sum_{j=1}^9 1 - \frac{1}{1-x^j}$.

As an extension, what is the solution to the general case (where we just did $M=9$)?