# Iterative Functional Equation

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?

-

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$.
Nice. How did you know to make that choice for $g_n(d)$? Where did the $667d$ come from? –  Gerry Myerson Jun 21 '11 at 5:31
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. –  Robert Israel Jun 21 '11 at 7:09
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. –  Yuval Filmus Jun 21 '11 at 8:04
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. –  Yuval Filmus Jun 21 '11 at 8:07