Showing that $f(x)=\frac x{x+1}$ is the unique function satisfying $f(x)+f\left(\frac1x\right)=1$ and $f(2x)=2f\big(f(x)\big)$

Solution 1:

For each coprime $n, m \in \mathbb N_+$, $f\left( \dfrac nm\right)=\dfrac{n}{n+m}$ is a solution.

To prove this, we induct on $n+m$. The base case is clearly true. Suppose it's true for $n+m\leq k$ for some natural number $k$ and consider $n+m=k+1$.

We consider two cases:

Case 1, $n>m$: Using the first condition and Case 2, we get that $$f\left(\dfrac{n}{m}\right) = 1 - f\left(\dfrac{m}{n} \right)=1-\frac{m}{m+n}=\frac{n}{n+m}\,\,\,\,\,\,\,\,\,\blacksquare$$

Case 2, $m>n$: By the condition, we can assume $m=n+l$ for some natural $l$. Then,

\begin{align*}f\left( \dfrac{n}{m}\right)=f\left( \frac{n}{n+l}\right) = f\left( f\left( \frac{n}{l}\right)\right) = \frac 12f\left( \frac{2n}{l}\right) = \frac{n}{2n+l} = \frac{n}{n+m}\,\,\,\,\,\,\,\,\,\,\blacksquare \end{align*}

Finally, we plug the function in and see that it indeed satisfies the conditions.

This was problem B4 of Ireland MO 1991.

Solution 2:

As j___d does, I will attempt to prove that $f(\frac pq) = \frac{p}{p+q}$ by strong induction on $p+q$, starting with the base case $p+q=2$ where $f(\frac11) = \frac12$.

Now assume that $f(\frac{p}{q}) = \frac{p}{p+q}$ holds when $p+q<k$, and consider fractions $\frac pq$ with $p+q=k$.

Whenever $p<q$, we have $f(\frac{p}{q-p}) = \frac pq$, so $2f(f(\frac{p}{q-p})) = 2f(\frac pq)$, and by the second identity this implies that $f(\frac{2p}{q-p}) = 2f(\frac pq)$. Whenever $p>q$, of course, we have $f(\frac qp) = 1 - f(\frac pq)$ by the first identity.

Either way, this gives us $f(\frac{p'}{q'})$ for some different $\frac{p'}{q'}$ with $p'+q'=p+q$, in terms of $f(\frac pq)$.

Now we repeat the following process. Start with $f(\frac1{k-1}) = x$, and let $\frac pq = \frac1{k-1}$. Then repeatedly apply one of the identities $$f\left(\frac{2p}{q-p}\right) = 2f\left(\frac pq\right) \qquad \text{or} \qquad f\left(\frac qp\right) = 1 - f\left(\frac pq\right)$$ (preferentially the first) to get a different value $f(\frac{p'}{q'})$ in terms of $f(\frac{p}{q})$ and therefore in terms of $x$. Set $\frac pq = \frac{p'}{q'}$ and repeat. An example for $k=11$: \begin{array}{cccccccccc} f(\frac{1}{10}) & f(\frac{2}{9}) & f(\frac{3}{8}) & f(\frac{4}{7}) & f(\frac{5}{6}) & f(\frac{6}{5}) & f(\frac{7}{4}) & f(\frac{8}{3}) & f(\frac{9}{2}) & f(\frac{10}{1}) \\ x & 2x & 1-8x & 4x & 16x-1 & 2-16x & & 8x & & 32x-2 \end{array} Because there are finitely many values, we will eventually loop back to a value we have already seen, getting a second expression for it in terms of $x$. That expression will be different from the first, because the coefficient of $x$ doubles with every step from left to right in the table above. (In this case, we'll get $f(\frac1{10}) = 3 - 32x$, so $x = 3 - 32x$.)

So we can solve for $x$ and get some value for $f(\frac{1}{k-1})$, as well as all the other values we've encountered. If there are values in the table we haven't filled in yet, we can start this process again from those values, stopping when we get two expressions for the same unknown value, or an expression for a value we've already solved for.

(By the way, if $k$ is not prime, then we will have some fractions $\frac pq$ with $p+q=k$ which can be simplified, so we already know their values. In some cases, this lets us take a shortcut from the very beginning: for example, this will happen whenever $k$ is even.)

Eventually, we can fill in the entire table. This tells us that there's a unique solution for all $f(\frac pq)$ with $p+q=k$. But we know that $f(\frac pq) = \frac{p}{p+q}$ is consistent with the functional equation, so if we got some unique solution, that must be what we got.

By induction on $p+q$, we have $f(\frac pq) = \frac{p}{p+q}$ for all $p, q \ge 1$.

Solution 3:

A bit too long for a comment, but here's a start:

You have shown $f(1) = 1/2$, $f(2) = 2/3$ and hence $f(1/2) = 1/3$.

Plug $x = 1/2$ into your second identity to get $f(1) = 2f(f(1/2))$, i.e $1/2 = 2 f(1/3)$, i.e $\color{blue}{f(1/3) = 1/4}$. Thus, $\color{blue}{f(3) = 3/4}$ as well.

To get $f(4)$ and $f(1/4)$, we must use the second identity twice as well as the first identity. First $f(4) = 2f(f(2)) = 2f(2/3)$. In addition, $f(2/3) = 2f(f(1/3)) = 2f(1/4)$. Thus $f(4) = 4f(1/4)$ and since $f(4) + f(1/4) = 1$ by the first identity, $\color{blue}{f(4) = 4/5}$ and $\color{blue}{f(1/4) = 1/5}$. We also get $\color{blue}{f(2/3) = 2/5}$ and $\color{blue}{f(3/2) = 3/5}$.

Then $f(1/2) = 2f(f(1/4))$ gives $1/3 = 2f(1/5)$ to get $\color{blue}{f(1/5) = 1/6}$ and $\color{blue}{f(5) = 5/6}$.

To get $f(6)$ and $f(1/6)$, we try to repeat the arguments used for $f(4)$ and $f(1/4)$. First, $f(6) = 2f(f(3)) = 2f(3/4)$. In addition $f(2/5) = 2f(f(1/5)) = 2f(1/6)$. Alas, this is where my ad hoc calculations break down.

Hopefully, these simple calculations are useful to help others find the underlying structure necessary to continue.