Fall 2017, problem 55
Comments
edited on february 20
@Michel: Very nice! On the other hand someones of your tricks can be adapted to the true problem. In particular we have:
(1)$\qquad\quad$ Let $x$ be such that $f(x)=g(x)$. Then setting $y:=f(x)$, we have $f(y)=g(y)=y+1$
so that we can iterate, thus getting that property $f(z)=g(z)=z+1$ holds true in a whole half-line.
The proof of (1) is quite immediate: because of $f(x)=g(x)$, the functional equation $f(g(x))=f(x)+1$ becomes $f(y)=y+1$ where $y:=g(x)=f(x)$; in the same manner we get $g(y)=y+1$, that in particular implies $f(y)=g(y)$.
edited on march 20
I just added a new comment with better results
Superb exposition of how $f(f(n))=f(n)+1$ has infinitely many possible solutions for $f$, none of which are surjective, and all but one of which are not injective either.
However, there is a huge leap from the given equations $f\circ g=f+1$ and $g\circ f=g+1$ to the claimed equations $f\circ f = f+1$ and $g\circ g = g+1$. This leap requires proof.
The claimed equation for $f$ was used to show that $f(x)=x+1$ for $x\geq\min f(\mathbb{N})$, and in turn, this property was used to justify the equation marked with a ? in the following claim:
$g(1)\geq f(1)$ $\Rightarrow$ $1+f(1) = f(g(1)) =^? g(1)+1$ $\Rightarrow$ $f(1)=g(1)$.
So there is still work to do! But I think we are much closer. Sorry to only be critical, but I haven't solved it myself either
Yes the leap requires proof. I shoul have written " IF f=g then both functions satisfy the same functional equation..." I still think that it is interesting to see that many solutions for f do exist an therefore one should not make any assumption on the behaviour of f in order to solve the problem. I am more and more convinced that the solution must be in N but we have very little to play with if we do not make any assumption on f. What intrigues me is that f and g play a symetric role and that any conclusion on f can also apply to g. For instance f(n) cannot be equal to n for all n and this applies to g too. In this Christmas period I will have more time to think ! As POW is for me a place to exchange ideas I value your critical eye ,pity that you do not live next door to me: we could then have interesting discussions !
I think the key is the observation you made in passing that if $f\circ f=f+1$, then $f(n)>n$ for all $n\in\mathbb{N}$. If we could somehow show that $f\circ g=f+1$ and $g\circ f=g+1$ implied $f(n)>n$ and $g(n)>n$ for all $n\in\mathbb{N}$, then we could just argue as follows:
1) if $(\forall n\in\mathbb{N}) f(n)>n$, then $1+f(n)=f(g(n))>g(n)$, so $f(n)\geq g(n)$.
2) if $(\forall n\in\mathbb{N}) g(n)>n$, then $1+g(n)=g(f(n))>f(n)$, so $g(n)\geq f(n)$.
3) And then together $f(n)\geq g(n)$ and $g(n)\geq f(n)$ imply $f(n)=g(n)$.
So how do we prove that $f(n)>n$ and $g(n)>n$ for all $n\in\mathbb{N}$?
That's easy for $n=1$: $g(f(n))=g(n)+1\neq g(n)$, so $f(n)\neq n$, and similarly $g(n)\neq n$. Thus, $f(1)\neq 1$ and $g(1)\neq 1$, so $f(1)>1$ and $g(1)>1$.
But now I'm stuck for $n=2$. Why must we have $f(2)>2$? We know $f(2)\neq 2$, but what goes wrong if $f(2)=1$? I think if we can understand this specific case, it will generalize.
We are definitly getting closer... I will use the symetry between f an g ie: if f(2) cannot be 1 then g(2) cannot be 1 either. Now assume that f(1)=2 an g(2)=1 then g(f(1))=g(2)=g(1)+1=1 Contraiction.
Now since f(n) is larger than n for n=1 an n=2 let us proceed by induction and assume that f(n) is larger or equal to n+1.
We have
f(g(f(n)))=f(g(n)+1)=f(f(n))+1
now f(f(n)) is larger or equal to f(n)+1 in turn larger or equal to n+2.
We therefore have f(g(n)+1) larger or equal to n+3.But by symetry g(n) is larger or equal to n+1 so that m=g(n)+1 is larger or equal to n+2 with minimum value at n+2.
So we have that if f(n) is larger than n then f(n+2) is larger than n+2. As f(n-1) is larger than n-1, we can conclue that f(n+1) is larger than n+1 an the induction is complete.
Am I wrong ?
Yes, if $g(2)=1$, there is an easy contradiction if $f(1)=2$. But what if $f(1)=100$? Then all we can easily say is $100=f(1)=f(g(2))=f(2)+1$, so $f(2)=99$, which is totally possible. Where do we go now to get our contradiction?
I tried looking at $f\circ f+1= (f\circ g)\circ f = f\circ(g\circ f) = f\circ(g+1)$ and $g\circ g+1 = g\circ(f+1)$, as you did above. They look like they will be very useful because they allow you to take a $+1$ inside the function argument and pull it outside (at the cost of switching between $f$ and $g$ inside the argument).
The problem with applying induction to these equations is that the assumptions $f(k)>k$ and $g(k)>k$ only hold for $1\leq k\leq n$. You're on your own for $k\geq n+1$. Thus, if we try to apply the induction assumption to $f(f(k=n))+1 =^{\textrm{VALID}} f(k\geq n+1)+1 =^{\textbf{INVALID}} (k\geq n+2) +1$.
So we cannot correctly conclude $f(f(n))\geq f(n)+1$, because $f(n)$ is (by hypothesis!) beyond the grasp of the induction hypothesis.
1) I have checcke the cases g(2)=1 together with f(1)=3,4,5,6 and all of them show at some stage a contradiction, the larger f(1) the more tedious it gets because a number of choices have to be made for some values of f(n) and all choices have to be tried before concluding that the is a contradiction in all cases. So I suspect that with a lot of work one could show that there there is also impossibility for f(100) for some n smaller than 100 but I have no proof for that.
2) You have shown that f(n) larger than n implies f=g: Interestingly f(n) and g(n) smaller than n+2 for alln also imply f=g. I could not, however, recover this property from the equation f(f(n))=f(n) +1
3) Back to the huge leap which needs proof ! I would argue the following. Suppose I take a function g(n) satisfying g(g(n))=g(n)+1 and ask the qustion: what should f(n) be like if f and g satisfy the given pair of equations ?
We have f(g(g´(n)))=f(g(n))+1=f(n)+2 but using the property of g we get:f(g(g(n)))=f(g(n)+1)=f(g(f(n)))=f(f(n))+1 So we see that if f and g satisfy the given pair of equation, then one class of solutions is that both satisfy an equation of the type: f(f(n))=f(n)+1. My analysis of this last equation indicated that f must be equal to g.Of course the proof is not complete as there may be other solutions for f and g which do not satisfy f(f(n))=f(n)+1.
Let us examine the functions $ f(x) $ and $g(x)$ : $ \mathbb{R^{+}} \rightarrow \mathbb{R^{+}}$, assuming they are continuous & differentiable. Differentating our given functional equation set with respect to $x$ yields:
$g'(x) \cdot f'(g(x)) = f'(x)$ (i)
$f'(x) \cdot g'(f(x)) = g'(x)$ (ii)
which rearranging and equating (i) with (ii) produces:
$f'(g(x)) = \frac{f'(x)}{g'(x)} = \frac{1}{g'(f(x))} \Rightarrow f'(g(x)) \cdot g'(f(x)) = 1$ (iii)
Since (iii) holds true for all $x \in \mathbb{R^{+}}$, the slopes $f', g'$ must be constant-valued, positive inverses of each other (i.e. $f$ and $g$ must be monotonically strictly-increasing linear functions). If we now change our mapping from $\mathbb{R^{+}} \rightarrow \mathbb{R^{+}}$ to $\mathbb{N} \rightarrow \mathbb{N}$, our results should be of the form:
$f(n) = An + B$ (iv)
$g(n) = \frac{1}{A}n + C$ (v)
Substituting (iv) and (v) into the original functional equation set now yields:
$f(g(n)) = f(n) + 1 \Rightarrow A(\frac{1}{A}n + C) + B = (An + B) + 1 \Rightarrow n + AC = An + 1$, or $\boxed{A = C = 1}$
$g(f(n)) = g(n) + 1 \Rightarrow \frac{1}{A}(An + B) + C = (\frac{1}{A}n + C) + 1 \Rightarrow n + \frac{B}{A} = \frac{1}{A}n + 1 $, or $\boxed{A = B = 1}$
Thus, $\boxed{f(n) = g(n) = n + 1; n \in \mathbb{N}}$.
I only assume that both functions are bijective in N .This means that f(n) or g(n) must be equal or larger than n for some n.
Suppose now that f is strictly larger than g then we have f(n) +1 strictly larger than g(n)+1=g(f(n)) for all n.
This in turn means that g(f) is equal or smaller than f for all n and hence g(n) is equal or smaller than n for all n.
As g(n)=n does not comply with the equations, we cannot have f strictly larger than g.
As g plays a symetric role we can only have f=g.
The existence of at least one $x$ such that $g(x)>x$ holds true under no injectivity assumptions.
By absurde, let us assume that for any $y$ it is $g(y)\le y$. Then $g(g(y))\le g(y)$ and because of $g(y)\le y$, we have $g(g(y))\le y$; then, by induction, $g^k(y)\le y\quad\forall k,\quad$ where $g^k$ denotes the $k$-times composition $g_°g_°..._°g$.
Thus the family $\{g^k(y)\}_{k=1,2,...}$ is bounded, and also bounded is its image under $f$, say the family $\left\{f\big(g^k(y)\big)\big|k=1,2,...\right\}$. This is absurde because of $f\big(g^k(y)\big)=f\big(g^{k-1}(y)\big)+1=...=f(g(y))+k-1=f(y)+k$.
addendum A similar argument shows that, for any x, the sequence $\{ a_n:=f^n(x)\}:{n=0,1,2,\dots}$ contains no repeated values; in particular there exist numbers $m$ as big as one wants such that $f(m)>m$ (e.g. $m$ of the form $f^n(x)$ for big $n$)
@Michel, There are many holes in that argument.
1) The assumption that $f$ and $g$ are bijective is false. $f(n)=g(n)=n+1$ works, and neither $f$ nor $g$ is surjective -- there is no $k\in\mathbb{N}$ such that $f(k)=1$ or $g(k)=1$.
2) Why should the assumption that $f(n)>g(n)$ for at least ONE $n$ then imply $f(k)+1>g(k)+1=g(f(k))$ for ALL $k$?
3) And even if it were true that $f(k)+1>g(f(k))$ (and thus $f(k)\geq g(f(k))$) for all $k\in\mathbb{N}$, it would not follow that $m\geq g(m)$ for all $m\in\mathbb{N}$, because $f$ is not necessarily surjective, as noted in (1) above.
@Claudio, Here's a briefer argument to show $(\exists n\in\mathbb{N}) g(n)>n$: Since $f(g(1))=f(1)+1\neq f(1)$, $g(1)\neq 1$. Since $g(1)\in\mathbb{N}$, we have $g(1)>1$.
Thank you Claudio and Matthew for those useful comments, I was indeed too quick to post my answer. This being said, we are now left with a solution whose assumtion requires both functions to be continuous and differentiable, assumtion which is much stronger than say f is surjective in N- (1) . I have the feeling that this strong assumtion is not necessary as one can imagine many functions with values f(n) =n+1 and which are not continuous or differentiable between those values in R+. With the knowledge that there is at least one n for which both f and g (which play a symetric role) are larger than n , can you mend my proposal or suggest a solution while staying in N ?
A small observation: If $f = g$ then the range of $f$ and $g$ is either empty or $\mathbb N$, because anytime any $a\in$ range $f$, then $a+1$ is in range $f$. Assuming that the range is not empty, then it must be that $f(n) = g(n) = n+1$, since $f(f(n)) = f(n)+1$ and $g(g(n)) = g(n)+1$.
And a simple case: Assume that $f(n) = g(n) + c$ for some constant integer $c$, for all $n$, (that is, we just restrict our attention to functions $f$ and $g$ offset by some constant $c\neq 0$). Doing some tricks, we can see that
$f(g(f(g(n)) = f(f(g(n)) + 1 = g(f(g(n)) + 1 + c = g(g(n)) + 2 + c = f(g(n)) + 2 = f(n) + 3$
and by experimenting, we can conclude that $(fg)^k(n) = f(n)+k+1$, and similarily $(gf)^k(n) = g(n)+k+1$.
Then $(fg)^kf(n) = f(f(n)) + k + 1=g(f(n)) + k + 1 + c = g(n)+k+2+c$. But this is also equal to $f (gf)^k(n) = f(g(n)+k+1)$. Since this is true for any integer $k$, let's look at $k = c-1$. Then $f (gf)^k(n) = f(g(n)+c) = f(f(n)) = g(f(n)) +c = g(n)+c+1$. So that means that $g(n)+2c+1 = g(n)+c+1$, which implies $c = 0$.
Not sure how to generalize it though; cool problem!
Let me add another (trivial, but maybe useful) remark: If $g(n)>n\ \forall n$ then $f(m)\le g(m)\ \forall m$.
The proof is by absurde: we simply show that the existence of $m$ such that $ f(m)>g(m) $ implies that $g(n)\le n$ for $n:=f(m)$. And in fact $g(f(m))=g(m)+1\le f(m)$.
Of course the assumption that the graphs of both $f$ and $g$ are above the diagonal implies $f=g$.
Added on January, 29 Even better, denoting by $R(f)$ the range of $f$, we have: $$\{g(x)>x\quad \forall x\in R(f)\}\Longleftrightarrow\{f(y)\le g(y)\quad \forall y\}$$ and the (non decreasing) monotonicity of $g$ is a sufficient condition for the property $g(x)>x\quad \forall x\in R(f)\quad$The proofs are quite simple.
We want to prove that a sufficient condition is given by: $$\text{ One among }f\text{ and }g\text{ is non decreasing. }$$
The proof easely follows from the statements (1),...,(5) here down; some property was already pointed out by other contributors.
(1) No $x$ can satisfy $f(x)=x$. In fact we would have $g(x)=g(f(x))=g(x)+1$.
(2) If $g$ is constant on $(a,b)$, also $f$ is constant on $(a,b)$. In fact, let $g(x)=k$ for $x\in(a,b)$; then, for $x\in(a,b)$ it is $f(x)+1=f(g(x))=f(k)$, say $f(x)=f(k)-1$.
(3) $\{g\text{ is non decreasing}\}\ \Longleftrightarrow\ \{f\text{ is non decreasing}\}.$ Let us show that $n\le m$ implies $f(n)\le f(m)$. We can confine ourselfs to the case of $g(n)$ < $g(m)$ (in fact monotonicity only says that $g(n)\le g(m)$, but (2) gives directly the result if $g(n)=g(m)$). Thus our starting point is $n$ < $m$ and $g(n)$ < $g(m)$ that also implies $g(f(n))\le g(f(m))$. Due to the monotonicity of $g$ (that forces $\{g(a)\le g(b)\}\ \Longleftrightarrow\ \{a\le b\text{ or }g(a)=g(b)\}$) we get $f(n)\le f(m)$ (say our thesis) or $g(f(n))=g(f(m))$; but the last property gives $g(n)+1=g(m)+1$ and this was excluded.
(4) $\{g\text{ is non decreasing}\}\ \Longrightarrow\ \{f(x)>x\ \forall x\}$. We have $f(1)>1$ because of (1). We want to prove that monotonicity of $g$ implies that the set $\mathbb E$ of the $x$ satisfying $f(x)\le x$ is empty. Remark that, because of (1), we can also define $\mathbb E$ as the set of $x$ satisfying $f(x)$ < $x$. By absurde, let us assume that $\mathbb E$ is not empty; then it has a minimum, that we call $m$; then for $m':=m-1$ we have $f(m') > m'$, say $f(m')\ge m'+1\equiv m$. The monotonicity then implies $f(m)\ge m$ or, due to (1), $f(m)>m$. This is absurde because $m\in\mathbb E$.
(5) $\{f(n)>n\ \forall n\}\ \Longrightarrow\ \{g(m)\le f(m)\ \forall m\}$. By absurde, let $m$ be such that $g(m)>f(m)$; then $f(n)\le n$ for $n:=g(m)$ because of $f(g(m))=f(m)+1\le g(m)$; that is $f(n)\le n$.
After all these comments I woul offer the following :
-Both functions f an g satisfy the same functional equation in N f(f(n)) = f(n)+1 for all n
We now look at the solutions of this equation.The initial value f(1) generates an infinity of values for f(n) an hence defines the function in N. As poimted out before f(1) cannot be 1 as it does not comply with the functional equation.
If f(1) =2 then f(2)=3 , f(3)=4 an more generally f(n)=n+1
If f(1)=3 then f(3)=4,f(4)=5 an then more generally f(n)=n+1 except for n=1and f(2) can be set arbitrarily different from 2 and 1
If f(1) =a then f(a) = a+1 and more generally f(n)=n+1 for n equal or larger than a. For n smaller than a then f(2),f(3) ..f(a-1) can be set arbitrarily with the condition that f(n) is larger than n: Ineed f(n)=n is impossible from the functional equation . Furthermore suppose f(b)=a withn b larger than a, then f(f(b))=f(a)=f(b)+1=a+1 ,then f(a+1)=a+2 etc... until we reach f(b) which is larger than a :contradiction.
Now suppose that f(1)=a an g(1) =b and that WLOG b is equal or larger than a.
f(g(1))=f(b)=b+1=f(1)+1=a+1 then a=b
Now in turn take f(2)=c and g(2)=d with the same reasoning as above (using either f(g(n)) or g(f(n)) depening on the relative values of c and d) we conclude that c=d.
This can be done up to f(a-1) and we then conclude that f(n)=g(n) for all n. Note in passing that the class of suitable functions is larger than n+1.