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
Someone please help.
 A: 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.
A: I'm not confident about this answer but i'll post it anyways, since there's no answers.
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.
