Iterated Function $f(f(x))$

Algebra Level 4

$f: \mathbb{R} \rightarrow \mathbb{R}$ is a function such that
$f\big(f(x)\big) = x^2 - x + 1.$ What is the value of $f(0)$ to 2 decimal places?

The answer is 1.00.

4 solutions

Zach Abueg
Dec 14, 2017

We can see that $f(f(0)) = 1$ and $f(f(1)) = 1$ .

Now consider $f(f(f(x)))$ . If $f(f(x)) = x^2 - x+ 1$ , then $f(f(f(x))) = f(x)^2 - f(x) + 1$ .

Plugging in $f(f(0))$ , we have

$f(f(f(0))) = f(1) = f(0)^2 - f(0) + 1$

$\begin{aligned} f(0)^2 - f(0) + 1 - f(1) = 0 \qquad \color{#3D99F6}{(1)} \end{aligned}$

Similarly, plugging in $f(f(1))$ gives us

$f(f(f(1))) = f(1) = f(1)^2 - f(1) + 1$

$f(1)^2 - 2f(1) + 1 = \left(f(1) - 1\right)^2 = 0$

Thus, $f(1) = 1$ . Using $\color{#3D99F6}{(1)}$ , this implies that

$f(0)^2 - f(0) + 1 - 1 = f(0)^2 - f(0) = 0$

$f(0) (f(0) - 1) = 0$

which gives us $f(0) = 0$ or $f(0) = 1$ . It must only be one of these, since $f$ is a function.

Assume that $f(0) = 0$ . Then $f(f(0)) = f(0) = 0$ , which contradicts $f(f(0)) = 1$ . Thus, $f(0) = \boxed{1}$ .

As Calvin has pointed out in the comments, this solution is not complete without showing whether or not such a function $f$ exists.

Note: For completeness, we should ensure that such a function exists. It might be possible that we nailed down a value for $f(1), f(0)$ , but there is a contradiction further down the road.

Calvin Lin Staff - 3 years, 5 months ago

True, this is all assuming that such a function exists. I don't think I can prove the existence or nonexistence of $f$ , so I'll let someone else fill in for me.

Zach Abueg - 3 years, 5 months ago

Vivek Khatri
Dec 17, 2017

put f(×)=× then equation becomes f(×)= (f(×))^2 -- f(×) +1

What is your point? The function $f(x) = x$ does not satisfy $f(f(x)) = x^2 - x + 1$ . Furthermore, $f(0) \neq 0$ .

Calvin Lin Staff - 3 years, 5 months ago

Théo Leblanc
Aug 26, 2019

In response to @Calvin Lin , I think I can prove the existence of functions satisfying the condition.

Actually it is a proof of existence and I haven't managed to find an explicit example of theses functions (very frustrating...).

First consideration:

$x^2-x+1=(x-1/2)^2+\frac{3}{4}=P(x)$

There is a symetry with respect to $x=1/2$ . Therefore we only need to show that there exists a function $f: x\in[1/2; +\infty[ \mapsto f(x) \geq 1/2$ satisfying $f(f(x))=x^2-x+1$ and prolong the function so that it is even with respect to $1/2$ ie $f(x+1/2)=f(1/2-x)$ ie $f(x)=f(1-x)$ .

First step, on $[1/2;1[$ :

Let $f(1/2)=a\in]1/2;3/4[$ (it's point $A_0$ on the image bellow).

this gives us the value of $f(a)=P(1/2)$ (it's point $A_1$ ).

Now we define $f$ on $[1/2;a]$ by the segment $[A_0A_1]$ .

Now for every point $(x,f(x))$ on this segment we will do this "transformation":

Note that $A_1$ is the transformed point of $A_0$ . So because this transformation is continuous (both $P$ and the first part of $f$ are) we create a new continuous curve wich define $f$ between $A_1$ and $A_2$ (the transformed point of $A_1$ ).

Because the first part of $f$ (which is continuous) and $P$ are strictly increasing, the second part of $f$ is well defined (exactly one value is given to $f(x)$ for each $x$ ) and also strictly increasing. (You have to convince yoursefl that all of that is true).

Repeat this process to create the third part of $f$ with the second etc.

I will prove (by contradiction) that eventually we will have defined $f$ on $[1/2;1[$ :

Suppose we never reach x-coordinates greater than $b<1$ . So because $f$ is continuous, increasing, and bounded ( $id \leq f \leq P$ because $P$ is increasing) $f$ can be prolong by continuity at $x=b$ . It has to be $f(b)=b$ either we weren't stuck.

Therfore $A_n=(x_n,y_n) \underset{n\to +\infty}{\longrightarrow} (b,b)$ .

By construction, $x_{n+1}=y_n$ and $y_{n+1}=P(x_n)$ , so by continuity, $P(b)=b$ and this is wrong !

Note: by induction, $\forall n, \ x_n<1$ .

Recap: We have defined $f$ on $[1/2;1[$ and by constuction, $f(f(x))=P(x)=x^2-x+1$ .

Next step: set $f(1)=1$

$f(f(1))=P(1) \ \checkmark$

Final step: on $]1;+\infty[$

Because we can't start at $+\infty$ or at $1$ (we are on $]1;+\infty[$ ) we have to "start in the middle" and create $f$ on the right and on the left.

Let $x_0>1$ and $x_0<y_0=f(x_0)<P(x_0)$ (that is point $A_0$ ).

Create $A_1=(x_1,y_1)$ like in the first step and define $f$ on $[x_0;x_1]$ by the segment $[A_0A_1]$ .

Exaclty like in the first step, construct $A_{-1}$ and a second part of $f$ etc etc. The same demonstration holds and on $]1,x_0]$ it is done.

Construct also $A_2$ , $f$ between $[A_1A_2]$ etc. Remark: by "induction" $x<f(x)<P(x)$ because $P$ is strictly increasing. This ensure that $f$ is well defined (never two or more value for one $x$ ).

$note: $Q$ is the reverse of $P$$ note: $Q$ is the reverse of $P$

We finally just need to prove that we can continue this as far as we want ( ie $x_n\longrightarrow +\infty$ , where $A_n=(x_n,y_n=f(x_n))$ ).

It is easy to remark that $u_{n+1}+u_n=P(x_n)-x_n \geq P(x_0)-x_0>0$ where $u_n=x_{n+1}-x_n > 0$ .

So it is impossible that $u_n\longrightarrow 0$ , so $\displaystyle\sum_{n\in\mathbb{N}} u_n$ diverges. Thus, $x_n\longrightarrow +\infty$ .

$Illustration of $u_{n+1}+u_n=P(x_n)-x_n$. Same color means same lenght. Orange: $u_n$, Green: $u_{n+1}$$ Illustration of $u_{n+1}+u_n=P(x_n)-x_n$ . Same color means same lenght. Orange: $u_n$ , Green: $u_{n+1}$

Hence, $f$ is well defined and by construction, $f(f(x))=x^2-x+1 \ \square$

Here's how I created the functions:

(First, for simplicity assume that the domain is $x \geq \frac{1}{2}$ .)

Define $P(x) = x^2 - x + 1$ .

Step 1: For any $x \geq \frac{1}{2}$ , define $F_x = \left ( \{ z | \exists n \text{ such that } P^{n} (z) = x \} \cup \{ z | \exists n \text{ such that } P^{n} (x) = z \} \right) \cap \{ z | z \geq \frac{1}{2} \}$ .
Show that this defines an equivalence relation on $x \geq \frac{1}{2}$ .
There are uncountably many classes, which we classify below:
Type A: $x = 1$ . $\{1\}$ belongs in it's own class. All other equivalance classes have infinitely many elements.
Type B: $x < 1$ . There is a natural map $T$ from $F_x \rightarrow \mathbb{N}$ as follows: Let $\alpha$ be the smallest element of $F_x$ , then define $P^n( \alpha) \rightarrow n+1$ .
Type C: $x > 1$ . There is a map $T$ from $F_x \rightarrow \mathbb{Z}$ as follows: Pick a representative $\alpha$ , and define $P^n (\alpha) \rightarrow n+ 1$ .

Step 2: We now define the function in the following way:

Pick 1 representative of each equivalence class. Pair up representatives that belong in the same type (as an ordered pair)
Type A: Define $f(1) = 1$ .
Type B: For every pair $(x,y)$ , let $\alpha$ be the smallest element of $F_x$ and $\beta$ be the smallest element of $F_y$ . Define $f ( P^n(\alpha) ) = P^n ( \beta )$ and $f( P^n(\beta) ) = P^{n+1} ( \alpha )$ for $n \in \mathbb{N}$ .
Type C: For every pair $(x,y)$ , define $f( P^n (x) ) = P^n (y)$ and $f( P^n (y) ) = P^{n+1} (x)$ ) for $n \in \mathbb{Z}$ .

Step 3:
Show that any function defined in this manner satisfies the conditions, since $f(f(x) ) = P(x) = x^2 - x + 1$ .

Notes:
1. You are assuming the function must be continuous, which need not be true.
2. In your solution, when you say "Now we define $f$ on $[1/2, a]$ by the segment $A_0 A_1$ ", you are essentially choosing the pairing in step 2 Type B. Similarly for "Final step: on $( 1, \infty )$ ." With these choices, we can guarantee that the function is continuous. However, the function will likely not be differentiable.
3. Interestingly, we can show that if $x > 1$ , then $f(x) > 1$ . Likewise, if $\frac{1}{2} \leq x < 1$ , then $\frac{1}{2} < x < 1$ . I didn't expect this when I first wrote this up (and then had to go back and define Type B/C)
4. (I believe that) There is a solution which is a smooth function (All nth derivatives exist and are continuous) on $( \frac{1}{2}, 1 )$ .

Now, we extend the domain to $\mathbb{R}$ .

Step 1: No change

Step 2: - For $x < \frac{1}{2}$ , observe that $f(x) = f(1-x)$ or $1 - f(1-x)$ . However, we're not completely free to choose which value (which is the point of this question).
- Define $f(0) = 1$ .
- For $x < \frac{1}{2}, x \neq 0$ , define $f(x) = f(1-x)$ or $1 - f(1-x)$ . However, there are some restrictions here, namely that if $f(x) = 1 - f(1-x) < \frac{1}{2}$ , then we must have $f ( 1 - f(1-x) ) = f(f(1-x))$ (IE It cannot be $1 - f(f(1-x)$ . )

Step 3: No change. (Do you see where the new condition is applied?)

Notes:
1. You are assuming that $f(x) = f(1-x)$ , which need not be true.
2. (I believe that) This gives us a complete classification of all solutions.

Calvin Lin Staff - 1 year, 9 months ago

I have some questions about the way you construct these functions:

your equivalence relation is $\forall x,y\geq 1/2, \ x\sim y \ \text{iff} \ \exists n, P^n(x)=y \ or \ P^n(x)=y$ ? If yes, I'm OK.
For type B and C, when you introduce $T$ , are you claiming that $F_x=\{ P^n(\alpha), \ n\in\mathbb{N} \}$ (type B) and $F_x=\{ P^n(x), \ n\in\mathbb{Z} \}$ (type C) where $P^{-n}(x)=Q^n(x)$ for $n\in\mathbb{N}^*$ where $Q$ is the reciprocal of $P$ on $[1/2;+\infty[$ ? (To me it is true, correct me if I'm wrong)
Clarification for the pairing in step 2: Each class has 1 representative which is paired only once, right? Either you have contradictions.
In step 2 when you define $f$ for type C pairs, shoudn't be $n\in\mathbb{Z}$ either you miss points in the neighborhood of $1$ ?

I struggle a little for $x<1/2$ but for $x\geq 1/2$ I'm fine and yes you are right when I define the first part of $f$ (the segment) I only choose a pairing !

Théo Leblanc - 1 year, 9 months ago

Yes.
Yes. The idea of $T$ is to explain why (say) $F_ { 0.75}$ cannot map to an element in $F_{2}$ , because we do not have a linear transformation from $\mathbb{N} \rightarrow \mathbb{Z}$ .
Yes. That's what picking representative of equivalence classes means. I've edited the phrasing slightly.
Yes, this is edited. (Note: I mixed up some $\mathbb{N}$ and $\mathbb{Z}$ . This should be fixed now.)

Yea, the case of

z < \frac{1}{2}

is tricky, it took me a while to work through. Here is how I thought about it.

Quasi-bijective property: We know that if $f(x) = f(y)$ , then $x^2 - x + 1 = f(f(x)) = f(f(y)) = y^2 - y + 1$ , hence $x =y$ or $1-x = y$ . If both numbers are $\geq \frac{1}{2}$ (resp $\leq \frac{1}{2})$ , then we can conclude that $x = y$ .

For clarity of notation, when I use $x$ , it refers to a real number $\geq \frac{1}{2}$ . When I use $z$ , it refers to a real number $< \frac{1}{2}$ .

We know that $f((f(1-x)) = (1-x)^2 - (1-x) + 1 = x^2 - x + 1 = f(f(x) )$ .
Can $f(1-x)$ map to any real number $x_1 \geq \frac{1}{2}$ ? From $f(x_1) = f ( f( 1-x) = f(f(x))$ , and applying the quasi-bijective property, we get that $x_1 = f(x)$ . This is the only possible value $\geq \frac{1}{2}$ .
Can $f(1-x)$ map to any other real number $z_1 \leq \frac{1}{2}$ ? We have $f(z_1) = f(f(1-x)) = x^2 - x + 1 \geq \frac{1}{2}$ . Hence, $f(f(z_1)) = f( x^2 - x + 1 ) = f(f( 1 - z_1 ) )$ . Applying the quasi-bijective property, $f(1-z_1) = x^2 - x + 1 = f(f(x))$ , and again $1 - z_1 = f(x)$ . Hence $f(1-x) = z_1 = 1 - f(x)$ . Furthermore, in this instance, we require $f(z_1) \geq \frac{1}{2}$ .

Here is an explicit example. Suppose we chose $f(2) = 4$ , which then forces the chain $f(4) = 3, f(3) = 13, f(13) = 7$ etc.
Let's consider what $f(-3)$ could be.
Case 1: we could have $f(-3) = f(1 - 4) = f(4) = 3$ . If so, this places no restriction on any other value.
Case 2: we could have $f(-3) = f(1-4) = 1 - f(4) = -2$ . However, this places the restriction that $f(-2) = f(f(-3)) = (-3)^2 - (-3) + 1 = 13$ . In addition, we have the restriction that $f(-1 ) \neq -3$ , since otherwise we get the contradiction $3 = f(f(-1)) = f(-3) = -2$

Calvin Lin Staff - 1 year, 9 months ago

@Calvin Lin – Thank you, I got this! It is a little bit tricky sometimes with the quasi-bijective proprety but it's OK!

One last question: (I am not enough skillful with axiom of choice, so that is just a "intellectual curiosity" question)

Are you allowed to pair representative of each equivalence class ? I mean, there is an uncountable infinite amount of equivalence class (axiom of choice...). Moreover, it is not a problem for type B, you choose the smallest element as representative but you can't for type C, and again is it allowed to choose one representative (without telling how) for every class..? Maybe taking the closest to $a>1$ is a way of doing it but we will miss some functions...

Théo Leblanc - 1 year, 9 months ago

I will look at your classification carefully tonight.

Yes I only find functions satisfying some more restrictive properties but it is just to make my construction easier. For example I need continuity and that $f$ is strictly increasing between $A_nA_{n+1}$ to ensure that I define $f$ exactly once for all $x$ 's between $A_{n+1}A_{n+2}$ . (Bolzano–Weierstrass theorem)

I also could have choose any strictly increasing curve between $A_0A_1$ , not just a segment.

Théo Leblanc - 1 year, 9 months ago

Calvin Lin Staff
Dec 14, 2017

[This is not a solution.]

Note: There are infinitely many functions that satisfy the conditions. However, we must have $f(1) = 1$ , $f(0) = 1$ .

Can you find a "non-nice" function?

Put f(×)=x then equation becomes f(×)=( f(×))^2 -- f(×) +1 solving this quadratic equation we get only one value of f(×) that is 1

Vivek Khatri - 3 years, 5 months ago

Be careful with such substitutions, and avoid making your notation do double duty.

What you technically mean is to make the substitution $x = f(y)$ . In which case, you get $f(f(f(y))) = f(y)^2 - f(y) + 1$ .

Note that we cannot "Put f(×)=x then equation becomes f(×)=( f(×))^2 -- f(×) +1". Do you understand the error that you made?

Calvin Lin Staff - 3 years, 5 months ago

Nice solution. I have one mathematical problem related to the differential equation. Can you help for that? my Gmail address is jinjaladinesh@gmail.com. If you can provide any help for that then, please comment in the section or just mail me your mail address to make contact with you. Thank you in advance. Best regards, Dinesh Jinjala

Dinesh Jinjala - 3 years, 5 months ago

You can post it as a discussion .

Calvin Lin Staff - 3 years, 5 months ago

Iterated Function f ( f ( x ) ) f(f(x)) f ( f ( x ) )

The answer is 1.00.

4 solutions

0 pending reports

Iterated Function $f(f(x))$