# Functional Equation of iterations

Problem: Let $f : \mathbb{Q} \to \mathbb{Q}$ satisfy $$f(f(f(x)))+2f(f(x))+f(x)=4x$$ and $$f^{2009}(x)=x$$ ($f$ iterated $2009$ times).

Prove that $f(x)=x$. This is a contest type problem so it is supposed to have an elegant solution.

My approach: I considered $f^{(k)}(x)=a_k$ then we get,

$a_n+2a_{n-1}+a_{n-2}-4a_{n-3}=0$ with $f(a_{n-1})=a_n$ and we need to show that the sequence is constant, $a_i=a_0$. The characteristic root of that recurrence are not good. Also I observed that f must be a bijection

• If $f(x)$ is a polynomial of degree $n$, then the left hand side has degree $n^3$. – user332714 Jun 9 '16 at 16:07
• @lastresort , oops! Yes. So, f can be any function. – Subham Jaiswal Jun 9 '16 at 16:41
• @lastresort How do we know that $f$ is a polynomial? – GFauxPas Jun 9 '16 at 17:00
• @GFauxPas, i had mentioned possibility of f being a polynomial, n ow its edited – Subham Jaiswal Jun 9 '16 at 17:19
• @GFauxPas Before the edit it read "Even if anyone can do this for polynomials please tell me". – user332714 Jun 10 '16 at 9:59

I'm not sure that my solution is elegant.

So let $g(x) = f(x) - x$. We may rewrite the first equation from task as $$f(f^2(x)) - f^2(x) + 3f^2(x)-3f(x) + 4f(x) - 4x = 0,$$ or using $g(x)$ $$g(f^2(x)) + 3g(f(x)) + 4g(x) = 0.$$ Let $a_n = g(f^n(x))$. Then $a_n + 3a_{n-1} + 4a_{n-2} = 0$. We may make this recurrent relation simpler: let $b_n = a_n + \frac{3 - i\sqrt{7}}{3}a_{n-1}$. Then $b_n + \frac{3+i\sqrt{7}}{2}b_{n-1} = a_n + 3a_{n-1} + 4a_{n-1} = 0$ or $$b_n = -\frac{3+i\sqrt{7}}{2}b_{n-1} = \left(-\frac{3+i\sqrt{7}}{2}\right)^{n-1} b_1.$$ Now using relation $f^{2009}(x) = x$ we get that $b_{2010} = b_1$. Thus $$b_1 = \left(-\frac{3+i\sqrt{7}}{2}\right)^{2009} b_1 \; \Rightarrow \; b_1 = 0\; \Rightarrow \; b_n = 0.$$ Thus $a_n + \frac{3 - i\sqrt{7}}{2}a_{n-1} = 0$ or $$a_n = \left(-\frac{3 - i\sqrt{7}}{2}\right)a_{n-1} = \left(-\frac{3 - i\sqrt{7}}{2}\right)^{n}a_0$$ and again, as $f^{2009}(x) = f(x)$ we get $a_{2009} = a_0$ or $$a_0 = \left(-\frac{3 - i\sqrt{7}}{2}\right)^{2009}a_0 \;\Rightarrow\; a_0 = 0.$$ As $a_0 = g(x) = f(x) -x$ we get $$f(x) - x = 0$$ QED.

Look at the equation $f^{3} + 2f^{2} + f = 4x$.

This tell us that the left hand terms are a linear combination of $x$ summing up to $4x$, unless any of them cancel eachother out.

Suppose none of the left hand terms cancel out.

Then $f^3 + 2f^2 + f = ax + bx + f$

$f = x(4 - a - b)$

Combine this with the fact that $f^{2009} = x$ and it follows that $f = x$

Now we just need to check what happens if any combination of the LH terms cancel.

Suppose that ALL of the LH terms cancel out. Then the equation makes no sense, we can discard the case.

Suppose that $f^3$ and $2f^2$ cancel eachother out, we can arrive at the result using the results from the previous two suppositions.

Suppose $f$ and $f^3$ cancel eachother out, we get

$f^2 = 2x$

$f^4 = 2^{2}x$

...

$f^{2010} = f(x) = 2^{1005}x$

This contradicts the fact that $f^{2009} = x$, so they shouldn't cancel out.

Finally suppose that $f$ and $f^2$ cancel eachother, we get
$f^3 = 4x$

$f^6 = 16x$ ...

$f^{2010} = f(x) = 4^{670}x$

This contradicts the fact that $f^{2009} = x$, so they shouldn't cancel out.

Done.