Find all functions $ f: \mathbb{N} \rightarrow \mathbb{N}\; $ satisfying

$$ f(f(f(n))) + 6f(n) = 3f(f(n)) + 4n + 2001 , \forall n \in\mathbb{N} $$

After some trial and error I assumed the solution to be of the form $ f(n) = n + r\;$ which gave me $ f(n) = n + 667\; $ as a solution but I am unable to come up with any other solutions. How would you guys solve this problem?

Thanks in advance.


Given $n \in \mathbb{N}$, define $$ g_n(d) = f^{(d)}(n) - 667d. $$ Routine computation yields the recurrence equation $$ g_n(d+3) = 3g_n(d+2) - 6g_n(d+1) + 4g_n(d). $$ The characteristic polynomial is $$ x^3 - 3x^2 + 6x - 4 = (x-1)(x^2-2x+4). $$ The two roots of $x^2-2x+4$ are $2e^{\pm i \pi/3}$.

It follows from the general theory of recurrence relations that for some real $A,B$ and angle $\theta$, $$g_n(d) = A + B2^d \cos (d\pi/3 + \theta).$$ The cosine part is a periodic function in $d$ attaining $6$ fixed values, at least one of them strictly positive and at least one strictly negative. In particular, if $B \neq 0$ then for some $e \in \{0,\ldots,5\}$ we have $$C \triangleq B\cos (e\pi/3 + \theta) < 0.$$ This implies that $$f^{(6d+e)}(n) = g_n(6d+e) + 4002d + 667e = A + 2^d C + 4002d + 667e $$ is eventually negative. This contradicts the premise that $f \geq 0$, and so $B = 0$. Substituting $d = 0$ in the formula for $g_n$, we deduce that $g_n(d) = A = n$ and so $$ f^{(d)}(n) = n + 667d. $$ In particular, $f(n) = n + 667$.

  • 4
    $\begingroup$ Nice. How did you know to make that choice for $g_n(d)$? Where did the $667d$ come from? $\endgroup$ – Gerry Myerson Jun 21 '11 at 5:31
  • 1
    $\begingroup$ Hindsight is always 20-20. Knowing that $f^{(d)}(n) = n + 667d$ is a solution, you notice that subtracting $667 d$ gives you something simpler. $\endgroup$ – Robert Israel Jun 21 '11 at 7:09
  • 1
    $\begingroup$ Conversely, $667d$ is the term you need to subtract in order to get a homogeneous recurrence relation. Alternatively, instead of subtracting it we get a non-homogeneous recurrence relation. To solve it, we need to solve the corresponding homogeneous relation, and add some fixed solution to the non-homogeneous recurrence. We already know that $667d$ is such a solution, and we continue as before. I thought that presenting it the way I did is cleaner, although the derivation was along the lines just described. $\endgroup$ – Yuval Filmus Jun 21 '11 at 8:04
  • $\begingroup$ As for choosing to look at iterates of $f$, this is suggested by the form of the functional equation. Moreover, lately I have been working on something that involves solving a non-homogeneous recurrence relation (though with non-constant coefficients), so this "solution pattern" suggested itself after a short while. $\endgroup$ – Yuval Filmus Jun 21 '11 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.