# A functional recursion problem..do you have any idea?

I have a problem which is related to algebra and polynomials. I would be very grateful if any of you could give a hand to solve it. Here is the problem: Consider the function $f_0(x) =x(1-x)$ and for $n \geq 0$ define $$f_{n+1}(x) =\frac 12 (f_n(x^2) + f_n((1-x)^2)).$$ Now, looking more closely at $f_0(x)$, we see that it is increasing on $[0,\frac 12]$ and decreasing on $[\frac 12, 1]$ . The problem is to prove that such a property holds for all the $f_n$'s. More precisely, prove that each $f_n (x)$ is increasing on $x \in [0,\frac 12]$ and decreasing on $x \in [\frac 12, 1]$ . I would be very thankful if any of you could help.

-
So we don't re-invent the wheel, it might be worth noting that some suggestions were made when this question was posted to MathOverflow, mathoverflow.net/questions/74175/… –  Gerry Myerson Sep 1 '11 at 6:56
One is going to need a stronger induction hypothesis than simply that $f_n$ is increasing then decreasing, because it doesn't hold for $f_0$ being a triangular function $1 - \lvert 2x - 1 \rvert$. –  Rahul Sep 1 '11 at 7:23