Proving equality of two functions

Lef $f, g$ be two $\mathbb{N}\rightarrow \mathbb{N}$ functions satisfying the following conditions.

• $f(g(n))=g(n)+1$
• $g(f(n))=f(n)+1$

Show that $f = g$.

I have tried a lot of things and got lots of results, none of which look promising.

• Just pedantry, but does your $\mathbb{N}$ include $0$ or not? Also what exactly did you try? – mdave16 May 13 '17 at 0:23
• How do you know it is true? – fleablood May 13 '17 at 1:31
• No I don't consider 0 – user379195 May 13 '17 at 6:56

Let $f(2n) = 2n; f(2n+1) = f(2n+2); g(2n) = 2n+1; g(2n+1)= 2n+1$. (i.e. $f$ takes $n$ to the first even number equal or larger than $n$. $g$ takes $n$ to the first odd number equal or larger than $n$.

Then $f(g(2n)) = f(2n+1) = 2n+2 = 2n + 1 + 1 = g(2n) + 1$

$f(g(2n+1)) = f(2n+1) = 2n+2 = 2n+1 + 1 = g(2n+1) + 1$

$g(f(2n)) = g(2n)=2n+1 = f(2n) + 1$

$g(f(2n+1)) = g(2n+2) = 2n + 3 = 2n+2 + 1 = f(2n+1) + 1$.

So the statement isn't true. But is true for all $n \in Im(f) \cap Im(g)$

Let $Deg(f(n)) = a$ and $Deg(g(n))=b$ such that $Deg(f)$ is the biggest power in the polynomial $f$.

For example : $Deg(2n^3+7n-5)=3$ and $Deg(-7n^5+3n^2+n)=5$.

Now it easy to see that $Deg(f(g(n))) - Deg(g(n)) = 0$ and $Deg(g(f(n)))-Deg(f(n))=0$, and since $Deg(f(g(n)),Deg(g(f(n)))= a b$.

We have few cases :

$a,b>1$ then $a b> a,b$ which means no polynomials of degree higher than $1$ can satisfy your condition.

$a=1, b>1$ then $a b = b$ but $a b \not= a$, also the same conclusion(without loss of generality).

$a=0,b>1$ then $a b =a$ but $a b \not= b$, also the same conclusion(without loss of generality).

$a=1,b=1$ then the only functions satisfy this are the functions $f(n)=n+1,g(n)=n+1$ and in this case $f(n)=g(n)$.

$a=0,b=1$ then $a b=a \not =b$ also the same conclusion(without loss of generality).

$a=0,b=0$ then $ab=a=b$ which means that you can not discard this situation using this method but setting $f(n)=c_0$ and $g(n)=c_1$ gives that there is no such constant polynomials.

In conclusion : if for any two polynomials $f(n),g(n)$ if $f(g(n))=g(n)+1$ and $g(f(n))=f(n)+1$ then $f(n)=g(n)$ and to be explicit $f(n)=g(n)=n+1$

Note : this answer is only about polynomial(not necessarily from integers to integers) but does not prove the general question about other kind of functions.

Let us note that by definition $f$ and $g$ are almost symmetrical, so any result proved for $g$ will have an analogous result for $f$. Now, we have that $g$ is $n+1$ on the image of $f$.

Consider the function $$gfgfgfgfg\dots(n),$$ where there are $m + 1$ applications of a function. By multiple uses of the starting relations, we get that $g(n) = n + 1$ if $n$ is of the form $g(m) + \text{odd}$ or $f(m) + \text{even}$. More concretely, for the case $m = 2$, $gfg(n) = fg(n) + 1 = g(n) + 2 = g(g(n) + 1)$. Similarly, we have that $f(n) = n + 1$ if $n$ is of the form $f(m) + \text{odd}$ or $g(m) + \text{even}$.

On a far different approach, if $f$ and $g$ commute, then we have that $f = g$. As then, $g(n) + 1 = fg(n) = gf(n) = f(n) + 1$ and so $f$ and $g$ are identical. I've tried to come up with functions which commute and satisfy the defining relations, but are not $n + 1$, as shown in @Ahmad's answer, I can't consider polynomials. So instead I give you for any fixed natural $k$

$$f(n) = g(n) = \begin{cases} k &\mbox{if } n = 0 \\ n+1 & \mbox{else } \end{cases}$$ As one can verify, these satisfy the defining relations but are not $n+1$ globally. So I don't think we should be heading down the path of showing that $f(n)=g(n)=n+1$, because as we see, there are solutions not of this form.

• There are even examples like $f(0)=2$, $g(0)=3$, and $f(n) = g(n) = n+1$ for $n \geq 1$ which show that $f \neq g$ is possible. – Zoe H May 13 '17 at 1:36

$\begin{cases} g(2n)=0 \\ g(2n+1)=2n+2 \end{cases}\qquad\begin{cases}f(2n)=2n+1 \\ f(2n+1)=1\end{cases}$

$f,g$ verifies the requirements, yet $f\neq g$

$\begin{array}{lll} f(g(2n))=f(0)=1 & g(2n)+1=1 & \checkmark \\ f(g(2n+1))=f(2n+2)=2n+3 & g(2n+1)+1=2n+3 & \checkmark \\ g(f(2n))=g(2n+1)=2n+2 & f(2n)+1=2n+2& \checkmark \\ g(f(2n+1))=g(1)=2 & f(2n+1)+1=2 & \checkmark \\ \end{array}$

• $N$ does not contain 0 – user379195 May 13 '17 at 7:09