27
$\begingroup$

We are given a function $f:\mathbb Q^+ \to \mathbb Q^+$such that $$f(x)+f(1/x)=1$$ and $$f(2x)=2f(f(x))$$ Find, with proof, an explicit expression for $f(x)$ for all positive rational numbers $x$.

Every number I have evaluated is of the form $f(x)=\frac{x}{x+1}$ and this clearly fits the functional equations, but I can't prove that it's the only solution. Can anyone help me? I have put down the start of my workings which led me to the conjecture of $f(x)=\frac{x}{x+1}$.

Plugging in $x=1$ clearly gives $f(1)=\frac{1}{2}$ and $f(2)=2f(f(1))=2f(1/2)$ which we can plug back into the first equation to get that $f(2)=\frac{2}{3}$. Working in this vein I have been able to show that $f(x)=\frac{x}{x+1}$ for particular values of $x$, but not in general.

The most difficult part appears to be proving it for the even integers. To prove $x=8$, we have $f(12)=2f(6/7)=4f(3/10)=4-4f(10/3)=4-8f(5/8)=8f(8/5)-4=16f(4/9)-4 = 32f(2/11)-4=64f(1/12)-4=60-64f(12)$, giving us $f(12)=12/13$. This will probably be the main area of difficulty in the proof.

$\endgroup$
  • 6
    $\begingroup$ I think what's needed is to show that $f(x) = x/(1+x)$ is the only solution, not just that it is a solution. $\endgroup$ – Connor Harris Apr 10 '17 at 14:28
  • $\begingroup$ @ConnorHarris That's what I meant anyway, but I don't know how to prove it is the only solution. For instance, proving it for particular even numbers is actually quite challenging, as you have to express it in terms of other values of the sequence until you reach the reciprocal of that number. $\endgroup$ – Cataline Apr 10 '17 at 14:51
8
+50
$\begingroup$

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$.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Maybe I'm missing something but how do we conclude that $f\left(\frac{2n}{l}\right) = \frac{2n}{2n+l}$? I mean we have that $2n+l = n + m + 2l > n+m = k+1$, so we can't use the iductive hypothesis. $\endgroup$ – Stefan4024 Apr 10 '17 at 15:33
  • $\begingroup$ Oops, I mixed up all the variables in the vital case. And I got 4 upvotes somehow :) I think it's correct now. $\endgroup$ – John Doe Apr 10 '17 at 16:04
  • 4
    $\begingroup$ @j___d Sorry, but it still doesn't make sense to me. We suppose that $n+m=k+1$. Then $2n+l=2n+m-n=m+n=k+1>k$, so the induction hypothesis can't be used. And $l$ must be coprime to $2n$, so the fraction can't be simplified further. $\endgroup$ – Cataline Apr 10 '17 at 16:27
  • $\begingroup$ Ah, you're absolutely right. Give me a minute to fix that. $\endgroup$ – John Doe Apr 10 '17 at 16:42
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I actually found this while trying the question, and so probably shpuld have put it in the description. To get $f(1/6)$ you then need to evaluate $f(4/3)=2f(2/5)=4f(1/6)$ which gets us $f(6)=2f(3/4)=2-2f(4/3)=2-8f(1/6)$ giving us $f(1/6)=1/7$. But you have to go through a long sequence of numbers to get the answer with this method, which makes proving anything difficult. $\endgroup$ – Cataline Apr 10 '17 at 15:00
  • 2
    $\begingroup$ I suspect what makes the problem challenging is discovering an underlying combinatorial structure which organizes these complicated calculations and gives a means of proving general calculations using (complicated) inductive arguments. $\endgroup$ – Michael Joyce Apr 10 '17 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.