Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 10 down vote accepted

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$.

share|cite|improve this answer
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
@Robert, thanks. – Gerry Myerson Jun 23 '11 at 6:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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