$LHS\ge 2$ and so $RHS\ge 2$ and so $f(n+1)\ge g(n+1)+1\ge 2$ $\forall n\ge 1$ and so $f(n)\ge 2$ $\forall n\ge 2$ So $LHS\ge 3$ $\forall n\ge 2$ and so $f(n+1)\ge g(n+1)+2\ge 3$ $\forall n\ge 2$ and so $f(n)\ge 3$ $\forall n\ge 3$ So $LHS\ge 4$ $\forall n\ge 3$ and so $f(n+1)\ge g(n+1)+3\ge 4$ $\forall n\ge 3$ and so $f(n)\ge 4$ $\forall n\ge 4$ ... And we easily get thru induction $f(n)\ge n$ $\forall n\ge 1$ So $f(n+1)=f^{g(n)}(f(n))+g^{f(n)}(n)+g(n+1)-1$ $\ge f(n)+1$ and $f(n)$ is increasing. If $f(n)\ge n+1$ for some $n$, then $f(f(n))\ge f(n+1)$ and so $f^{g(n)+1}(n)\ge f(n+1)$ and then $LHS\ge f(n+1)+1$ while $RHS \le f(n+1)$, impossible So $f(n)=n$ $\forall n$ and equation is $g^{n}(n)=2-g(n+1)$ and so $g(n+1)=1$ and $g(n)=1$ $\forall n\ge 2$ Setting $n=1$ in equation, we get then $g(1)=2-g(2)=1$ Hence the solution : $f(n)=n$ and $g(n)=1$ $\forall n\in\mathbb N$, which indeed is a solution.

Nice solution, Patrick! A relatively standard technique that can also be applied here is as follows: assume first that the minimum that $f$ takes is for some $N>1$, take $n=N-1$ in the proposed equation, and reach a contradiction, hence $f(1)<f(n)$ for all $n\geq2$. Now assume that $f(1)<f(2)<\dots<f(N)$ for some $N\geq1$, and $f(n)>f(N)$ for all $n>N$ (clearly true for $N=1$). It clearly follows that $f(n)\geq n$ for all $n\leq N$, and $f(n)>N$ for all $n>N$. Now work your way similarly to a contradiction if the minimum of $f(n)$ for $n\geq N+1$ happens for some $M>N+1$ (again taking $n=M-1$ in the proposed equation). By induction, we conclude that $f$ is strictly increasing, and consequently $f(n)\geq n$, while for all $n>m$, $f(n)-n\geq f(m)-m$. And the (IMHO) hard part of the problem is thus concluded... I have seen this technique somewhere before (can't remember where), applied on a different type of functional equation, but the idea behind the process for showing that $f$ is strictly increasing is similar. But your approach is much shorter and much more elegant! Edit: now I remember where I saw this "uglier" technique, some solution to problem 6 in IMO1977... Patrick's approach would not have worked in that problem, I think, but it works perfectly in this one!

My solution: Lemma 1: If $f(k)$ is minimum of $f$ than $k=1$. Proof: Let $k\in \mathbb N$ be a positive integer such that $f(k)$ is minimum of $f$. We have $f(n+1)-f^{g(n)+1}(n)=g(n+1)-1+g^{f(n)}(n)\ge 1$ so if $k>1$ plugging in $n=k-1$ we have that $ f^{g(k-1)+1}(k-1)\le f(k)-1$ which is contradiction so $k=1$. __________________________________________________________ Lemma 2: If $f(a)=1$ than $a=1$. Proof: If we have $f(a)=1$ it implies $f(a)\le f(n)$ for all $n\in\mathbb N$ so we have $a=1$ by Lemma 1. __________________________________________________________ Let $k' \in \mathbb N$ be a positive integer such that $f(k')\le f(n)$ for all $n\neq 1$. We have that $k'>1$ so plugging in $n=k'-1$ we have $f(k')-f^{g(k'-1)+1}(k'-1)=g(k')-1+g^{f(k'-1)}(k'-1)\ge 1$ so we have that $f(k')> f^{g(k'-1)+1}(k'-1)$ which implies $ f^{g(k'-1)}(k'-1)=1$ so by Lemma 2 applied consequently we have $f(k'-1)=1$ and $k'-1=1$ which implies $f(1)=1$ and $k'=2$. ________________________________________________________ Induction hypothesis: $f(k)=k$ and $f(A)=k \implies A=k$ for all $k\le n$. Proof for $n+1$: Let $a_{n+1}$ be positive integer such that $f(j)<f(a_{n+1})\le f(m)$ for all $m>n, j\le n$($n+1$'st smallest value of $f$(since $f$ is not constat it exists)). Plugging in $n=a_{n+1}-1$ we have $f(a_{n+1})-f^{g(a_{n+1}-1)+1}(a_{n+1}-1)=g(a_{n+1})-1+g^{f(a_{n+1}-1)}(a_{n+1}-1)\ge 1$ so we have $ f^{g(a_{n+1}-1)+1}(a_{n+1}-1)<f(a_{n+1})$ so $ f^{g(a_{n+1}-1)}(a_{n+1}-1)=j$ for some $1\le j\le n$ so by IH we have $f(a_{n+1}-1)=j$ and $a_{n+1}=j+1$ so we have since $a_{n+1}>n$ $j=n$ so $a_{n+1}=n+1$. Now let $a_{n+2}$ be $n+2$'nd minimum of $f$ that is $f(j)<f(a_{n+2})\le f(m)$ for all $m>n+1, j\le n+1$. Plugging in $a_{n+2}-1$ we have $f(a_{n+2})-f^{g(a_{n+2}-1)+1}(a_{n+2}-1)\ge 1$ and it implies $ f^{g(a_{n+2}-1)}(a_{n+2}-1)=n+1$(it has to be a number from $n+1,n,...,1$ but if it's $j<n+1$ that it would be $a_{n+2}=j+1$ which is contradiction). But now we have $n+1= f^{g(a_{n+2}-1)}(a_{n+2}-1)>n>n-1>...>1$ so we have that $ f^{g(a_{n+2}-1)}(a_{n+2}-1)$ is $n+1$ st minimum so actually $f(a_{n+1})=f(n+1)= f^{g(a_{n+2}-1)}(a_{n+2}-1)=n+1$. So we have proved both statements of IH therefore it's true for all $n\in \mathbb N$. ______________________________________ Now we have $g^{n}(n)+g(n+1)=2$ so $g(n)=1$ for all $n$. So the only solution is $f(n)=n,g(n)=1$ for all $n$ which indeed is s solution since $n+1-1+1=n+1$.

Note that $f(n+1)-g(n+1)$ is bounded below, as the LHS is positive, so consider $k=\min\limits_{n\ge 2} f(n)-g(n)$, and $x_0>1$ such that $f(x_0)-g(x_0)=k$. Note that this implies $f(x)>k$ for $x>1$. Then, we plug in $x_0-1$ into the assertion. The RHS is $k+1$, so we know that $f^{g(x_0)+1}(x_0-1)\le k$. Of course, if $x_0-1>1$, then the iterated $f$ will be greater than $k$, so we must have $x_0=2$. Considering $f(1)$, we know that if $f(1)>1$, then $f^{g(1)+1}(1)>k$, which is a contradiction, so we must have $f(1)=1$, which works. This also implies that $g(1)=k$. Now, we will do something very similar, namely consider $k_2=\min_{n\ge 3} f(n)-g(n)>1$, and $f(x_1)-g(x_1)=k_2$ for some $x_1>2$. A similar calculation gets us that $x_1$ must be $3$, and once again we have that $f(2)$ must be $2$. We can continue this process recursively to get $f(x)=x$. So, our assertion becomes $g^x(x)=2-g(x)$. $g$ is always a positive integer, so we must have $g(x)=1$. In conclusion, our only solution is $f(x)=x$ and $g(x)=1$.

Nice and easy! Here's my solution: Note that, for all $x \geq 2$, we have $$f(x)+1=f^{g(x-1)+1}(x-1)+g^{f(x-1)}(x-1)+g(x) \geq f^{g(x-1)+1}(x-1)+2 \Rightarrow f^{g(x-1)+1}(x-1)<f(x) \quad (\spadesuit)$$Order the elements in the range of $f$ as $f(x_1) \leq f(x_2) \leq \dots$ where $x_i$'s are positive integers. If $x_1>1$, then putting $x=x_1$ in $(\spadesuit)$ gives a contradiction to the minimality of $f(x_1)$; hence $x_1=1$ and $f(1)<f(x_2) \leq f(x_3) \leq \dots$ holds. Then if $x_2>2$, then on substituting $x=x_2$ in $(\spadesuit)$, we get $f(1)<f^{g(x_2-1)+1}(x_2-1)<f(x_2)$ which is not possible. So we have $x_2=2$, and $f(1)<f(2)<f(x_3) \leq \dots$ is also true. Continuing in this manner, we get that the $k^{\text{th}}$ smallest value in the range of $f$ is attained by $f(k)$ and all smaller values are distinct; in other words, we can say that $f$ is strictly increasing. Now, from the strictly increasing condition, we get $$1 \leq f(1) \leq f(2)-1 \leq f(3)-2 \leq \dots \leq f(n)-(n-1) \Rightarrow f(n) \geq n \quad \forall n \in \mathbb{N}$$Now, if for some $a \in \mathbb{N}$, we have $f(a)>a$, then $$a+1 \leq f(a) \leq f(a+1)-1 \leq \dots \leq f(m)-(m-a) \Rightarrow f(m) \geq m+1 \quad \forall m \geq a$$In particular this gives $$f^k(a)>f^{k-1}(a)>f^{k-2}(a)> \dots \Rightarrow f^k(a) \geq f^i(a) \quad \forall 1 \leq i \leq k$$where $k \in \mathbb{N}$. Putting $x=a+1$ in $(\spadesuit)$, we get $$f(a+1)>f^{g(a)+1}(a) \geq f(f(a)) \Rightarrow a+1 \geq f(a)$$where we use $g(a)+1 \geq 2$, and the fact that $f(m) \geq f(n) \Leftrightarrow m \geq n$. But this contradicts our original assumption. Thus, we get that $f$ must be the identity function. Then the problem statement translates to $g^n(n)+g(n+1)=2$. This is only possible if $g^n(n)=g(n+1)=1$. Varying $n$ over the set of integers then gives $g \equiv 1$. Hence, the only solution is $f=\text{id}$ and $g=1$, which clearly works. $\blacksquare$

For most of the solution, we use the FE in a very weak form. Indeed, since $g^{f(n)}(n),g(n+1)\ge 1$, we have \[Q(n):f(n+1)\ge f^{g(n)+1}(n)+1.\] Lemma: Fix some $k\in\mathbb{N}$. Then, $n\ge k\implies f(n)\ge k$. Proof: We induct on $k$ with $k=1$ trivial. Now suppose the lemma is true for some $k$. Then, for any $n\ge k$, \[Q(n)\implies f(n+1)\ge k+1,\]so we're done. $\blacksquare$ Lemma: We have $f(n+1)\ge f(n)+1$. Proof: By the previous lemma, \[f^{g(n)}(f(n))\ge f(n),\]so we're done by $Q(n)$. $\blacksquare$ Now for the main claim. Claim: We have $f(n)=n$ for all $n\in\mathbb{N}$. Proof: Fix some positive integer $n$, and say $f(n)=\ell\ge n+1$. Now suppose the statement $f(n+1)\ge r$ is true where $r\ge n+1$. By the second lemma, we then see that $f(t)\ge r$ for all $t\ge n+1$. Thus, \[f^{g(n)}(f(n)) = f(f^{g(n)-1}(\ell))\ge r\]since $f^{g(n)-1}(\ell)\ge \ell\ge n+1$ by the first lemma. Therefore, \[Q(n)\implies f(n+1)\ge r+1.\]Thus, the statement $f(n+1)\ge r$ implies $f(n+1)\ge r+1$, as long as $r\ge n+1$. However the first lemma implies it is true for $r=n+1$, so applying this repeatedly gives a contradiction, as desired. Thus $f(n)\le n$, so by the first lemma, $f(n)=n$. $\blacksquare$ Plugging this into the original FE gives \[n+g^n(n) = n+2-g(n+1),\]or \[g(n+1)=2-g^n(n)\le 1,\]so $g(n)=1$ for all $n\ge 2$. Plugging in $n=1$ into the FE gives \[g(2) = 2-g(1),\]so $g(1)=1$ also. Thus, $f\equiv\mathrm{id}$ and $g\equiv 1$, and this clearly works, so we're done.

The only solution is $(f,g)\equiv (n,1),$ which can be easily checked to work. Let $P(n)$ denote the assertion. $\textbf{Claim: }$ For all positive integers $k,$ we have $f(n)\ge g(n)+k$ for all $n>k.$ $\emph{Proof: }$ Induct on $k.$ For the base case, just note that if $n>1,$ then $P(n-1)$ yields \begin{align*}f(n)&=g(n)+f^{g(n-1)+1}(n-1)+g^{f(n-1)}(n-1)-1\\&\ge g(n)+1+1-1=g(n)+1.\end{align*}Now suppose the claim is true for $k,$ and assume there exists $n>k+1$ such that $f(n)=g(n)+k.$ From $P(n-1),$ we have $$f^{g(n-1)+1}(n-1)+g^{f(n-1)}(n-1)=k+1\implies f^{g(n-1)+1}(n-1)\le k.$$For all $m>k,$ we have $f(m)\ge g(m)+k>k$ by the inductive hypothesis. Thus, we must have $n-1\le k,$ contradicting our assumption that $n>k+1.$ $\blacksquare$ Note that the above claim implies that $f(n)\ge n$ for all $n.$ Now suppose $f(m)\ge m+1$ for some $m.$ Then, $P(m)$ yields $$f(m+1)-g(m+1)+1\ge m+1+g^{f(m)}(m)\implies f(m+1)\ge m+2.$$It follows by induction that $f(n)\ge n+1$ for all $n>m.$ Using this result, $P(m)$ yields $$f(m+1)-g(m+1)+1\ge m+g(m)+1+g^{f(m)}(m)\implies f(m+1)\ge m+3.$$By the same reasoning we used before, this implies that $f(n)\ge n+2$ for all $n\ge m+1.$ Again, using this new bound, $P(m)$ gives $$f(m+1)-g(m+1)+1\ge m+1+2g(m)+g^{f(m)}(m)\implies f(m+1)\ge m+4.$$Continuing in this manner, we can show that $f(m+1)$ is arbitrarily large, contradiction. Thus, $f\equiv n.$ Then it is easy to check that $g\equiv 1,$ so we are done.

We claim that $f(n) = n, g(n) = 1$ is the only solution. It is trivial to check it works. It turns out that it is enough to focus on the observation that \[f^{g(n)+1}(n) = f(n+1)-g(n)-g^{f(n)}(n) + 1 < f(n+1).\]Let $m$ be the $m\ge 2$ with $f(m) < m$ with minimal $f(m)$. Then take $n=m-1$ and observe that $f^{g(n)+1}(n) < f(m) \le n$. Then we have a contradiction. Either $n=1$, absurd, or $f(m')$ is the first minimal element of the sequence $f(f^k(n))$ with $0\le k\le g(n)$ yielding a contradiction. So this means that $f(n) \ge n$ for all $n$. Then observe that $f(n) < f(n+1)$, as otherwise $f(n+1) > f^{g(n)+1}(n) = f^{g(n)}(f(n)) \ge f(n) \ge f(n+1)$. So $f$ is increasing. Thus $n\le f^{g(n)}(n) < n+1$ because $f$ must be bijective. Then $f(n) = n$. Thus $n + g^{f(n)}(n) = n+1-g(n+1) + 1$, implying $g(n+1) = g^{f(n)}(n) = 1$. Thus all values of $g$ are $1$ by considering $n=1$, done.

The only such functions are $\boxed{f(n) = n}$ and $\boxed{g(n) \equiv 1}$ The idea is just to bound $f$ in terms of $g$ to get a contradiction. Since $f,g$ are always positive, we have $f(n+1)-g(n+1) + 1 \ge 1 + 1 \implies f(n) \ge g(n) + 1$ for all $n \ge 2$ So, if we take $n \ge 2$, we have that $f(n+1) - g(n+1) + 1 \ge f^{g(n)+1}(n) + g^{f(n)}(n) \ge 2 + 1 \implies f(n) \ge g(n) + 2$ for all $n \ge 3$ By induction, we get that $f(n) \ge g(n) + n-1$ for all $n$. In particular, this means $f(n) \ge n + (g(n)-1) \ge n$ Suppose that $f(n) \ge n+1$, then we have $f^k(n) \ge f^{k-1}(n+1) \ge f(n+1)$ But then, we have $f(n+1)-g(n+1) + 1 = f^{g(n)+1} + g^{f(n)}(n) \ge f(n+1) + g(\text{something})$, which is impossible since $g$ is positive. So, we have that $f(n) = n$ for all $n \in \mathbb{N}$ Putting this in the original equation, we get $g^n(n) + g(n+1) = 2$, which since $g$ is positive, means $g(n+1) = 1$ for all $n$. So, we just need to find $g(1)$. Putting $n = 1$ in the original equation, we have that $g(1) = 1$ and so we have $g \equiv 1$ and $f(n) = n$, as claimed. $\blacksquare$

daniel73 wrote: Nice solution, Patrick! A relatively standard technique that can also be applied here is as follows: assume first that the minimum that $f$ takes is for some $N>1$, take $n=N-1$ in the proposed equation, and reach a contradiction, hence $f(1)<f(n)$ for all $n\geq2$. Now assume that $f(1)<f(2)<\dots<f(N)$ for some $N\geq1$, and $f(n)>f(N)$ for all $n>N$ (clearly true for $N=1$). It clearly follows that $f(n)\geq n$ for all $n\leq N$, and $f(n)>N$ for all $n>N$. Now work your way similarly to a contradiction if the minimum of $f(n)$ for $n\geq N+1$ happens for some $M>N+1$ (again taking $n=M-1$ in the proposed equation). By induction, we conclude that $f$ is strictly increasing, and consequently $f(n)\geq n$, while for all $n>m$, $f(n)-n\geq f(m)-m$. And the (IMHO) hard part of the problem is thus concluded... I have seen this technique somewhere before (can't remember where), applied on a different type of functional equation, but the idea behind the process for showing that $f$ is strictly increasing is similar. But your approach is much shorter and much more elegant! Edit: now I remember where I saw this "uglier" technique, some solution to problem 6 in IMO1977... Patrick's approach would not have worked in that problem, I think, but it works perfectly in this one! Isn't this method wrong? At least when you try to reach a contradiction for $M > N+1$ by taking $n= M-1,$ we get that $f^{g(M-1)+1}(M-1)\leq f(M)-1 < f(M),$ but how do you know that $f^{g(M-1)}(M-1)$ is not less than $N$? You never showed the function was strictly increasing above $N$? Could somebody answer my doubts?

Assume we are only working on positive integers. Claim: $f(n)\ge n\forall n$. Proof: Since $LHS>2$, we have $f(n+1)-g(n+1)\ge 1\implies f(n+1)\ge 2\implies f(n)\ge 2\forall n\ge 2$. Now we take $n\ge 2$. Then we get $LHS>3$, so $f(n+1)\ge 3\implies f(n)\ge 3\forall n\ge 3$. Now we take $n\ge 3$. Then we get $LHS>4$, so $f(n+4)\ge 4\implies f(n)\ge 4\forall n\ge 4$. Proceeding similarly, we get $f(n)\ge k\forall n\ge k$, which proves our claim by setting $n=k$. Claim: $f$ is strictly increasing. Proof: We note that $LHS=f^{g(n)}(f(n))+g^{f(n)}(n)\ge f(n)+1$. So \[f(n+1)-g(n+1)+1\ge f(n)+1\implies f(n+1)-g(n+1)\ge f(n)\implies f(n+1)>f(n),\]which proves our claim. Now suppose there exists an $n$ so that $f(n)\ge n+1$. So we have $f^{g(n)}(f(n))\ge f(f(n))\ge f(n+1)$. Thus, $LHS>(n+1)$, but $RHS\le f(n+1)$, which is a contradiction. Thus, $f(n)=n\forall n$. Substituting this into the FE gives $n+g^{n}(n)=n+2-g(n+1)\implies g^{n}(n)=2-g(n+1)$. If $g(n+1)\ge 2$, then $g^{n}(n)\le 0$, a contradiction. So $g(n)=1\forall n\ge 1$. Setting $n=1$ gives $g(1)=1$. So the answer is $\boxed{f(n)=n\text{ and }g\equiv 1}$, which works.

Claim 1: $f(n)\geq n.$ Proof. $\forall n\geq 1$ we have $f(n+1)\geq g(n+1)+1\geq 2 \implies f(n)\geq 2 \forall n\geq 2.$ By induction, $f(n)\geq n.$ Q.E.D. Claim 2: $f\equiv \text{id},$ which fits. Proof. Note that $f(n+1)>f^{g(n)+1}(n).$ Assume the contrary. Then $f^{g(n)+1}(n)>f^{g(n)}(n)>\dots f(n),$ a contradiction. Q.E.D. Claim 3: $g\equiv 1,$ which fits. Proof. Follows directly after plugging in $f.$ Q.E.D.

Lemma 1: For all $x$, $x \le f(x)$. Proof: Use induction on $f(x)$. For the base case, we have $f(x) = 1$. Then, if $x > 1$, setting $n=x-1$ in the given condition gives that the RHS is $2 - g(x) \le 1$, but the LHS is at least 2 because it is the sum of two positive integers, contradiction. Therefore $x \le 1$. For the inductive step, suppose $f(x) = k$ for an integer $k \ge 2$. If $x = 1$, the claim is trivially satisfied, so assume $x \ge 2$. Then set $n=x-1$ in the given condition to get \[f^{g(x-1)+1}(x-1) + g^{f(x-1)}(x-1) = f(x) - g(x) + 1 = k - g(x) + 1 \le k.\]But $g^{f(x-1)}(x-1) \ge 1$, so $f^{g(x-1)+1}(x-1) \le k - 1$. Repeatedly applying the induction hypothesis to remove the $f$'s one by one gives $x - 1\le k-1$, or $x \le k = f(x)$, as desired. $\square$ Lemma 2: $f$ is increasing. Proof: For all $n$, we have \[f(n) \le f^{g(n) + 1}(n) = f(n+1) - g(n+1) - g^{f(n)}(n) + 1 \le f(n+1) - 1,\]so $f(n) + 1 \le f(n+1)$, as desired. $\square$ Lemma 3: $f(n) = n$ for all $n$. Proof: Let $f(n+1) = n + 1 + k$ for some nonnegative integer $k$, by Lemma 1. Then by the given condition, \[n \le f^{g(n) + 1}(n) = n - g(n+1) - g^{f(n)}(n) + k + 2 \le n + k.\]Now we claim $f^{g(n) + 1}(n) = n$, since otherwise, $f(n) \ge n + 1$ in order for $f(n) \neq n$ to hold, and \[n + k \ge f^{g(n) + 1}(n) \ge f(f(n)) \ge f(n+1) \ge n + 1 + k,\]where $f(f(n)) \ge f(n+1)$ comes from Lemma 2. This is a clear contradiction. Therefore $f^{g(n) + 1}(n) = n$, so $f(n) = n$, since otherwise $n = f^{g(n) + 1}(n) \ge f(n) \ge n + 1$, contradiction. $\square$ Now the condition simplifies to $g^{f(n)}(n) + g(n+1) = 2$, so $g(n+1) = 1$ for all $n$. Furthermore, setting $n=1$ gives $g(1) = 1$, so $g(n) = 1$ for all $n$. Therefore the only solution is $f(n) = n$ and $g(n) = 1$, which clearly works.

\[f(n+1)= f^{g(n)+1}(n) + g^{f(n)}(n) +g(n+1)-1\ge g(n+1)+1\ge 2,\forall n\ge 1\]\[f(n+1)= f^{g(n)+1}(n) + g^{f(n)}(n) +g(n+1)-1\ge g(n+1)+2\ge 3,\forall n\ge 2\]Keep doing it and obtain that $f(n)\ge n, \forall n\ge 1$ Suppose there exists $m\in \mathbb{N}$ so that $f(m)\ge f(m+1)$. This means that $f(f(m))\ge f(m)\ge f(m+1)$. Inductively, $f^k(m)\ge f(m+1), \forall k\ge 1$. Therefore \[f(m+1)-g(m+1)+1\ge f(m+1)+g^{f(n)}(n)\]which is obviously impossible. In other words, $f$ is increasing. Now suppose there exists $n_0\ge 1$ such that $f(n_0)>n_0$. This directly implies that $f(n)>n, \forall n\ge n_0$. Take such $N$. Then \[f(N)\ge N+1\Rightarrow f(f(N))\ge f(N+1)\ge N+2\]so inductively we have that $f^k(N)\ge N+k$. But plugging this in in the original equation gives \[f(N)\ge g(N)+g(N-1)+g^{f(N-1)}(N-1)+N\ge N+2\]And we can repeat this process infinitely many times, meaning that $f(N)\rightarrow \infty$, which is clearly a contradiction. Thus $f(n)=n,\forall n\ge 1$. The given equation can be written as \[g(n+1)+g^n(n)=2\]which means that $g\equiv 1$. In conclusion, the solution of the problem is \[\boxed{(f,g)=(1_{\mathbb{N}}, 1)}\]

We claim that $f(n)\ge n$ for all $n$. We prove this by induction on $k$, on the following statement: for all $n\ge k$, $f(n)\ge k$. Clearly the statement is true for $k=1$. Let $k=i$ work, then if $n\ge i$ \[f(n+1)=g(n+1)-1+f^{g(n)+1}(n)+g^{f(n)}(n)\ge n+1\]as desired. Now suppose $f(k)\ge k+c$ for some $k$, then we claim that $f(n) > n$ for all $n>k$. Indeed, a similar induction tells us that if $f(i)\ge i+c$ then \[f(i+1)=g(i+1)-1+f^{g(i)+1}(i)+g^{f(i)}(i)\ge i+1+c\]since $f^{g(i)+1}(i)\ge f^{g(i)}(i+c)\ge i+c$. In particular, \[f^{g(n)+1}(n)=f(n+1)-g(n+1)+1-g^{f(n)}(n)\le f(n+1)-1=n+c\]On the other hand, $f^{g(n)+1}(n)\ge f^2(n)=n+2c$ so $c=0$. Thus, $f(n)=n$ for all $n$. We have \[g^n(n)+g(n+1)=2\]so $g^n(n)=g(n+1)=1$ for all $n$. $g(n)=1$ for all $n$.

this one is particularly easy in comparison to the absolutely BRUTAL a3; also megarnie bro posted a sol TWO YEARS AGO how so oar were u even aime qual back then The only solution is f(n)=n,g(n)=1, which works. We'll first prove $f(n)\ge n$ by induction, with base case n=1 trivial. The inductive step follows from $f(n+1)=f^{g(n)+1}(n)+g^{f(n)}(n)+g(n+1)-1\stackrel{>f^{g(n)+1}(n)\quad(1)}{\ge f(n)+1}$. The extra statement on the top now finishes; $f(n)\ge n+1\implies f^{g(n)+1}(n)=f^{g(n)}(f(n))\ge f(f(n))\ge f(n+1)$, contradiction due to (1). We conclude that f(n)=n, and plugging in readily implies g(n)=1, for all n. $\blacksquare$