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.
 A: 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)$
A: 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. 
A: Disclaimer: Not a full answer, just some ideas I had.
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.
A: $\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}$
