Let $\mathbb{Q}^+$ be the set of all positive rational numbers. Find all functions $f:\mathbb{Q}^+\rightarrow \mathbb{Q}^+$ satisfying $f(1)=1$ and \[ f(x+n)=f(x)+nf(\frac{1}{x}) \forall n\in\mathbb{N},x\in\mathbb{Q}^+\]
Problem
Source: 2015 Taiwan TST Round 3 Quiz 2 P2
Tags: function, number theory, algebra, induction
26.04.2015 19:32
26.04.2015 21:14
let $x=1\implies f(n)=n, \forall n\in\mathbb{N^*}$. Let $x=n\implies f(\frac{1}{n})=1, \forall n\in\mathbb{N^*}$. We will prove $f(\frac{m}{n})=m,\forall m,n\in\mathbb{N^*},gcd(m,n)=1$ by induction on $|m-n|$.For $|m-n|=1$,we assume that $m>n \implies m=n+1\implies f(\frac{m}{n})=f(\frac{n+1}{n})=f(\frac{1}{n})+f(n)=n+1$. we have $f(\frac{n}{m})=f(\frac{n}{n+1})=f(\frac{2n+1}{n})-f(\frac{n+1}{n})=2f(n)+f(\frac{1}{n})-n-1=n$.Now suppose that the claim is true for $1\leq |m-n|<k$. For $m-n=k$ , we have $\exists ! q,r,0<r<n$ such that $m=nq+r$.There are 2 cases: Case 1:$q\geq2\implies f(\frac{m}{n})=f(\frac{r}{n})+qf(\frac{n}{r})$. we have $|m-n|>|n-r|$, from the induction hypothesis we get $f(\frac{m}{n})=r+qn=m$. $f(\frac{n}{m})=f(\frac{m+n}{n})-f(\frac{m}{n})=f(\frac{r}{n})+(q+1)f(\frac{n}{r})-m=n$. Case 2:$q=1\implies f(\frac{m}{n})=f(\frac{n}{r})+f(\frac{r}{n})$,$\exists ! q_1,r_1,0<r_1<r$ such that $n=q_1r+r_1\implies f(\frac{n}{r})=f(\frac{r_1}{r})+f(\frac{r}{r_1})$.Using the induction hypothesis and $|m-n|=r>|r-r_1|\implies f(\frac{n}{r})=f(\frac{r_1}{r})+q_1f(\frac{r}{r_1})=rq_1+r_1=n,f(\frac{r}{n})=f(\frac{n+r}{r})-f(\frac{n}{r})=f(\frac{r_1}{r}+q_1+1)-n=n+r-n=r$.In the same way, we proved $f(\frac{n}{m})=n$. We proved that the claim is true for $k$.Thus $f(\frac{m}{n})=m, \forall m,n\in\mathbb{N^*}, gcd(m,n)=1$ is the function satisfying the conditions of problem
26.04.2015 21:20
$x=1$ yields $f(n+1)=n+1$ for all positive integers $n$. Combined with $f(1)=1$, that's $f(n)=n$ for all positive integers $n$. $x=q$ for positive integer $q$ yields $f(\tfrac{1}{q})=1$, and $x=\tfrac{1}{q}$ gives $f(\tfrac{1}{q}+n)=1+nq$ for all positive integers $n$. Now let's get $f(\tfrac{p}{q})$ for $p<q$. We can do this with strong induction on $q$: assume you have $f(\tfrac{r}{s})=r$ for all $s<q$, $r<s$. Then $x=\tfrac{q}{p}$ yields $f(\tfrac{q}{p}+n)=f(\tfrac{q}{p})+nf(\tfrac{p}{q})$. We already know $f(\tfrac{q}{p}+n)$ and $f(\tfrac{q}{p})$ by the inductive hypothesis, so we're done. And the base case, $q=2$, is easy because $\tfrac{2n+1}{2}$ is the only guy we have to worry about, and we already have $f(\tfrac{2n+1}{2})=2n+1$. So $f(\tfrac{p}{q})=p$ where $\gcd(p, q)=1$.
24.07.2015 06:47
Note from $n=1$, $f(x+1) = f(x)+f(\frac{1}{x})$, and from $n=1$ again $f(x+2) = f(x+1)+f(\frac{1}{x+1}) = f(x)+f(\frac{1}{x})+f(\frac{1}{x+1})$. Now, $n=2$ yields $f(x+2) = f(x)+2f(\frac{1}{x})$ so $f(\frac{1}{x})=f(\frac{1}{x+1})$. Also, n=1 yields $f(x+1)=f(x)+f(\frac{1}{x})$, so whenever $x$ is a positive integer $f(x+1)=f(x)+1$. So for positive integers $x$ we have $f(x)=x$, $f(\frac{1}{x})=1$. Now, let $x=\frac{p}{q}$, $(p,q)=1$ and $p$, $q$ positive integers with $n=1$: So $f(\frac{p+q}{q})=f(\frac{p}{q})+f(\frac{q}{p})$. Let $x=\frac{p}{q}$, $n=2$, so $f(\frac{p+2q}{q}) = f(\frac{p}{q})+2f(\frac{q}{p})$. Let $x=\frac{p+q}{q}$, $n=1$: $f(\frac{p+2q}{q}) = f( \frac{p+q}{q}) + f(\frac{q}{p+q}) = f(\frac{p}{q})+f(\frac{q}{p})+f(\frac{q}{p+q})$. Equating with the result from the other gives: $f(\frac{p}{q})+f(\frac{q}{p})+f(\frac{q}{p+q})=f(\frac{p}{q})+2f(\frac{q}{p})$ and $f(\frac{q}{p+q})=f(\frac{q}{p})$. Excellent. I claim now that $f$ is just the numerator in the lowest terms. It's true for $\frac{p}{q}$ when $p=1$ or $q=1$. OK, assume it's not always true. Let $r$ be the rational of a minimal size (sum of numerator and denominator) with $f(r)$ not equal to the numerator of $r$. Note $r$ is not an integer. If $r<1$, we can write $r=\frac{q}{p+q}$ for some positive integers $(p,q)=1$. So then we get that $f(\frac{q}{p+q})=f(\frac{q}{p})=q$, as $\frac{q}{p}$ has smaller size. Oops. Note $f(1)=1$, so $r$ is not $1$, so assume $r>1$. We can write the fractional part of $r$ as $\frac{p}{q}$ for $0<p<q$, $(p,q)=1$, and then let $n>0$ be such that $r=\frac{p+nq}{q}$. Choose this $n$, and plug $x=\frac{p}{q}$. So $f(\frac{p+nq}{q}) = f(\frac{p}{q})+nf(\frac{q}{p}) = p+nq$ since $\frac{p}{q}$, $\frac{q}{p}$ are of size $p+q$ while $r$ has size $p+q+nq>p+q$. Again we get a contradiction, since $p+nq$ is exactly the numerator of $r$. So there are no rationals $r$ for which $f$ is not the numerator in lowest terms. Therefore this is the only possible function. To check that it works let $x=\frac{p}{q}$ in lowest terms, so $f(x+n)=f(\frac{p+nq}{q})=p+nq$, $f(x)=f(\frac{p}{q})=p, f(\frac{1}{x})=f(\frac{q}{p})=q$, and we get $p+nq=p+nq$, a true fact. Done.
11.05.2020 02:17
here's my solution let $P(x,n)$ the asertion $ f(x+n)=f(x)+nf(\frac{1}{x})$ $P(n,1) \implies f(n)=n \forall n \in \mathbb{N}$ comparing between $P(x,n+1)$ and $P(x+1,n)$ gives $f(\frac{1}{x})=f(\frac{1}{x+1})$ so $f(\frac{b}{a})=f(\frac{b}{a+b}) \dots (1)$ claim: if $gcd(a,b)=1$ then $f(\frac{a}{b})=a$ proof: we'll perform an induction on $a$ for $a=1$ just let $x \in \mathbb{N}$ suppose $f(\frac{c}{d})=c \forall c<b$ from (1) we have $f(\frac{b}{bk+r})=f(\frac{b}{r})=f(\frac{b-r}{r}+1)=f(\frac{b-r}{r})+f(\frac{r}{b-r})$ but $b > r$ and of course $b >b-r$ so by induction hypothesis $f(\frac{b-r}{r})=b-r$ and $f(\frac{r}{b-r})=r$ and so $f(\frac{b}{bk+r})=b$ $\blacksquare$ and we win
05.01.2025 15:09
Denote $P(x,n)$ the assertion of the given F.E. $P(1,n)$ gives $f(n+1)=n+1$ for all $n \in \mathbb Z_{>0}$ thus $f(n)=n$ for all $n \in \mathbb Z_{>0}$ since we are given $f(1)=1$, and now for $m \in \mathbb Z_{>0}$ we let $P(m,n)$ to get that $f \left( \frac{1}{m} \right)=1$, now from $P \left(\frac{1}{m}, n \right)$ we get $f \left(\frac{mn+1}{m} \right)=mn+1$ and now from $P \left(\frac{m}{mn+1}, 1 \right)$ gives $f \left(\frac{m}{mn+1} \right)=m$ , now observe the following, trivially we have $f\left(\frac{n}{2} \right)=\frac{n}{\gcd(2,n)}$ for all $n \in \mathbb Z_{>0}$ so $P \left(\frac{2n-1}{2},1 \right)$ gives $f \left(\frac{2}{2n-1} \right)=2$ and we know its $1$ when denominator is even so it's fine, to show how it would work one more time, notice from here that $f \left(\frac{2}{3} \right)=2$ and $f \left(\frac{3}{2} \right)=3$, and now using this and $P \left(\frac{2}{3}, n \right)$ gives $f \left(\frac{3n+2}{3} \right)=3n+2$, and like this now suppose inductively that we had $f \left(\frac{p}{n} \right)=\frac{p}{\gcd(p,n)}$ for $n \ge p$ and also $f \left(\frac{n}{p} \right)=\frac{n}{\gcd(p,n)}$ for all $n \ge p$ and this was true for all $p \le k$, we now prove it for $k+1$ (notice our base cases where $k=2,3$), from $P \left(\frac{k+1}{a}, 1 \right)$ for $a \le k$ we get that $f \left(\frac{a}{k+1} \right)=\frac{a}{\gcd(a,k+1)}$ so now $P \left(\frac{a}{k+1}, n \right)$ gives $f \left(\frac{a+n(k+1)}{k+1} \right)=\frac{a+n(k+1)}{\gcd(a,k+1)}$ which completes the first part, and for the second part we notice from here that if you let $b \ge k+2$ then from $P \left(\frac{b}{k+1}, 1 \right)$ we now get $f \left(\frac{k+1}{b} \right)=\frac{k+1}{\gcd(k+1,b)}$which completed the second part so our induction is completed. Therefore for any $\gcd(p,q)=1$ we have that $f \left(\frac{p}{q} \right)=p$ thus we are done .