Let f(n) be a function from the natural numbers from the natural numbers. Suppose further that f(1)=1, and assume that f(n) is equal to the number of positive integers k that are less than equal to n and satisfy f(k) | k. Then it is not hard to show that in fact f(n)=n. Now suppose we instead look at the exact same thing, but insist that f(n) count the number of k that are at most n and satisfy f(k)|P(k) where P is some fixed polynomial with integer coefficients.
For some choices of P, we do not have any function f which would satisfy the desired recursion. For example, if P(x)=x+1 we don't have any function f satisfying the recursion. To see this, note that we have either f(2)=1 or f(2)=2. If f(2)=1, then f(1)|1, and f(2)|2, so in fact f(2)=2. Consider the other case where f(2)=2. If so, since 2 does not divide 3, we must have f(2)=1. Contradiction and nd of p.
Here's my question which I have not been able to make substantial progress on: Are there any valid choices of P and f that satisfy the recursion and don't have f(n)=n for all n?