If we only plug b=1 we get $$f(a)=f^a(1)$$I think the rest will be easy

Nice Problem . Let $P(a,b): f^a(b) + f^b(a) \mid 2(f(ab) +b^2 -1)$, then by $P(a,1)$ we have that $f^a(1)=f(a)$, this give us the idea to prove injectivity. But also: $$f^a(b)= f^{a-1}(f(b))=f^{a-1}(f^b(1))=f^{a+b-1}(1)=f(a+b-1)$$Analogously we have $f^b(a)=f(a+b-1)$ then we define $Q(a,b): f(a+b-1) \mid f(ab) + b^2 -1$ Then combining $Q(a,b)$ and $Q(b,a)$ we have that $R(a,b) : f(a+b-1) \mid a^2 - b^2$ Case 1: Exists $a_0,b_0$ distinct positive integers such that $f(a_0)=f(b_0)$ Then we have that $f^{a_0}(1)=f^{b_0}(1)$ so the sequence $\{f^n(1)\}$ is bounded so $f$ is bounded. Claim: $f(f(1))=1$ Proof: We have that $R(b+1,b): f(2b) \mid 2b+1$, let $p=2b+1$ a prime very large then (using $f$ bounded) we have that $f(p-1)=1$. Let $k$ the minimum integer positive such that $f^k(1)=1$ but we have $f^{p-1}(1)=1$ so $k \mid p-1$. If we suppose that $k>2$ then by Dirichilet's theorem we can find a $p$ : prime very large such that $p \equiv k-1 \pmod k$ this implies that $k \mid 2$ !Contradicction¡ So we have $k \leq 2$ and this implies the claim. $\square$ Now we have $f(2k)=1$ and $f(2k-1)=f(1)$ and using $Q(2,2): f(3) \mid f(4)+3 \implies f(1) \mid 4$ so we need $f(1) \mid 4$ and it's easy prove that all this functions works. Case 2: The function is injective. This case is easy we have that $f^a(1)=f(a) \implies f^{a-1}(1)=a \implies f^{a}(1)=a+1 \implies f(a)=a+1$ so the unique function in this case is $f(x)=x+1$ that obvious works. We have found all the functions that satisfy the conditions of the problem. $\blacksquare$

mijail wrote: Let $k$ the minimum integer positive such that $f^k(1)=1$ but we have $f^{p-1}(1)=1$ so $k \mid p-1$. If we suppose that $k>2$ then by Dirichilet's theorem we can find a $p$ : prime very large such that $p \equiv k-1 \pmod k$ this implies that $k \mid 2$ !Contradicction¡ Dirichlet's Theorem is like overkiilling this problem! Just suppose the contrary that there exists $k>2$ such that there exists $N>0$ s.t for every $p \in \mathbb{P}$ and $p>N$, we have $p \equiv 1 \pmod k$ Then let all the prime that less than $N$ are $p_1,p_2,p_3, \ldots , p_n$. Now suppose $A$ to be $$ A = p_1p_2p_3 \ldots p_n \cdot k +2$$Then $(A,p_i)=1$ $\forall i=1,2,3 \ldots , n$, also since $A \equiv 2 \pmod k$, there exists a prime $q \ne p_i$ s.t $q$ is not congruent to $1$ modulo $k$ ( Contradiction) Thus $k \le 2$ and the remain can be dealt as you've done !

Firstly , we'll show the problem equation with $P(a,b)$. So for each number $a \in \mathbb{N}$ by $P(a,1)$ we have : $$f^a(1)+f(a)|2f(a)$$which obviously gives as that the equality $f(a)=f^a(1)$ holds. And by comparing $P(a,b)$ , $P(b,a)$ one can see that : $$f^a(b)+f^b(a)=f^{a-1}(f(b))+f^{b-1}(f(a))=2f^{a+b-1}(1)=2f(a+b-1) \implies f(a+b-1)|f(ab)+b^2-1 (I) \implies f(a+b-1)|a^2-b^2$$So by this result one can see that for each natural number $n \in \mathbb{N}$ we have $f(n)|2(n+1)$ and for all even numbers $n$ , $f(n)|n+1$ holds. Now suppose that there exist an odd number $n$ , such that $f(n)=1$ , then there exist an even number $k$ , such that the numbers $k , k-1$ are both coprime to $n$ , and note that $f(nk)=f^{nk}(1)=f^n(f^{n(k-1)}(1))=1$ , if we show the equation $I$ with $Q(a,b)$ , then one can see that : $$Q(n,k) \implies f(n+k-1)|k^2 , f(n+k-1)|n+k \implies f(n+k-1)|gcd(k^2 , n+k-1)=1$$So we have $f(n+k-1)=1$ and if we put $m_k=n+k-1$ , then since $gcd(n , m_k)=1$ without losing the generality by Bezout theorem there exist numbers $r , s \in \mathbb{N}$ such that $rn+1=sm_k$ and we can get : $$f(1)=f(f(rn))=f^{rn+1}(1)=f^{sm_k}(1)=f(sm_k)=1 \implies \forall a \in \mathbb{N} : f(a)=1$$So in other case , we can suppose that for an even number $n$ , $f(n)=1$ and by considering an odd number $k$ coprime to $n$ and such that $gcd(n , k-1)=2$ , same as above we can get $f(2)=1$ and for each even number $n$ , $f(n)=1$. Now since for each odd number $n$ , we have $f(n)=f(f(n-1))=f(1)$ and $f(1)|4$ then all odd values can give us number $2$ or all $4$ which easily one can see that both of these functions work on our equation. Now suppose that there doesn't exist such a number $n$ , that $f(n)=1$, and in this case , first we'll show that for all even numbers $n$ , $f(n)=n+1$. Firstly suppose that $a$ is an even number , then if for a natural $b$ we have $f(a)=f(b)$ , then $a=b$ ( mid-injectivity ). Because if $b$ is even and we have $b=a+2t$ , then for each number $k$ we have: $$f(a+2tk)=f^{a+2tk}(1)=f^{2t}(f^{a+2t(k-1)}(1))=f^{a+2t}(1)=f(a)$$And we can choose such a $k \in \mathbb{N}$ such that $a+1$ and $2tk$ are coprime and as the result , $gcd(a+1 , a+2tk+1)=1$ , so since $f(a)|a+1$ and $f(a+2tk)=f(a)|a+2tk+1$ , then $f(a)=1$ which is a contradiction. ( And this will obviously implies the odd case for $b$ too. ) Now suppose that for each even number $n$ , $n+1=p_{1}^{\alpha_1}...p_{s}^{\alpha_s}$ for primes $p_1 , ... , p_s$ and by induction on $\sum {\alpha_i}$ we'll show that $f(n)=n+1$. Firstly for an odd prime $p$ we have $f(p-1)|p$ and while $f(p-1)>1$ , we have $f(p-1)=p$ , now consider $f(n)|p_{1}^{\alpha_1}...p_{s}^{\alpha_s}$ and for each number $d|n+1$ that $d<n+1$ the value of $\sum \alpha_{i}$ is less than this value for $n+1$ , and by our induction case $f(d-1)=d$ . As the result , by mid-injectivity we have $f(n)=n+1$ for all even numbers. Now for each odd number $n$ while $f(n+1)=f(f(n))$ and $n+1$ is even , by our mid-injectivity we have $f(n)=n+1$. So we're done.

The answer is $f(n)=1$ for all $n$, or $f(n)=n+1$ for all $n$, which clearly work. Step 1: $f^k(1)=f(k)$. Proof: This can be attained by setting $b=1$, giving $$f^k(1)+f(1)\mid 2f(k)\implies f(k)<f^k(1)+f(k)\leq 2f(k)\implies f^k(1)=f(k)$$as needed. Step 2: $f(p-1)=1$ or $p$ for all odd primes $p$. Proof: Substituting $a,b$ and $b,a$ in the original, and subtracting, gives $$f^a(b)+f^b(a)\mid a^2-b^2$$Let $b=\frac{p-1}{2}$ and $a=\frac{p+1}{2}$ for some odd prime $p$. From step 1, $f^a(b)=f^{a+b-1}(1)=f(a+b-1)$ and $f^b(a)=a+b-1$. Thus, $$f(p-1)\mid p\implies f(p-1)=1,p$$as needed. Step 3: If some $f(k)=1$, then $f(n)=1$ for all $n$. Proof: If $f(k)=1$ for some $k$, then take $k$ to be minimal. Then the sequence $1,f(1),f(f(1)),\ldots$ is periodic with period $k$. Thus, if we set $a_i=f^i(1)$ for $0\leq i\leq k-1$, then for any $n\in\mathbb N$ with $n\equiv j\pmod k$ then $f^n(1)=f^j(1)=a_j$. We will show $a_i=1$ for all $0\leq i\leq k-1$. From step 1, since $f^a(b)=f^{a+b-1}(1)=f(a+b-1)$ and $f^b(a)=a+b-1$ we can rewrite the condition as $$f(a+b-1)\mid f(ab)+b^2-1$$Substitute $a=1$, giving $$f(b)\mid f(b)+b^2-1\implies f(b)\mid b^2-1\implies a_i\mid (nk+i)^2-1$$for all positive integers $n$, implying $a_i\mid \gcd(n^2k^2+2nki,i^2-1)$ for all $n$, so $a_i\mid \gcd(k,i^2-1)\mid k$. Due to $k$'s minimality, the numbers $1,f(1),\ldots, f^{k-1}(1)$ must be pairwise distinct, otherwise a shorter cycle exists (shorter cycles must include $1$ due to $k$'s existence). But $a_i$ must all be $k$'s factors, and $k$ has less than $k$ factors unless $k=1$ or $k=2$. If $k=2$, then reiterating $f^k(1)=f(k)$ gives $f(2n)=1$ and $f(2n+1)=2$ for all positive integers $n$. Substituting $(2n,2n)$ gives $$f(4n+1)\mid f(4n)+(2n)^2-1\implies 2\mid 4n^2-1$$a contradiction, so $k\neq 2$ giving $k=1$. Thus, $f(1)=1$ as desired, and reiterating $f^k(1)=f(k)$ we have $f(n)=1$ for all $n$. Step 4: If $f(n)\neq 1$ for all $n$, then $f(n)=n+1$. Proof: From step 2, we have that $f(p-1)=p$. Thus, the sequence $1,f(1),f(f(1)),\ldots$ has no repeating terms, as if there is a repeating term, then it contains a cycle and thus finitely many elements but $f^{p-1}(1)=f(p-1)=p$ and there are infinitely many odd primes $p$, a contradiction. Thus, if $f(a)=f(b)$ for $a\neq b$, then $f^a(1)=f^b(1)$, a contradiction. Thus, $f$ is injective. Now, since $f(a)=f^a(1)=f(f(a-1))$ we have that $f(a-1)=a$ from injectivity, so $f(n)=n+1$ for all $n$ as needed.

We uploaded our solution https://calimath.org/pdf/IranMO2021-N2.pdf on youtube https://youtu.be/G9GmO8s_EXs.

Solved with math_comb01 Claim: $f^a(1) = f(a)$ Proof Take $P(a, 1)$ to get $f^a(1)+f(a) \mid 2f(a)$, but $f(a) < f^a(1)+f(a)$, so we must have that $f^a(1)+f(a) = 2f(a)$, so $f^a(1) = f(a)$ Claim: If $f$ is not injective, then $f \equiv 1$ Proof Clearly, if $f(a) = f(b)$ for distinct $a, b$, then the arrows graph of $f^k(1)$ eventually cycles back due to the previous claim, so $f$ is eventually periodic. $P(1, a)$ gives $f(a) \mid a^2-1$. Letting $a$ range over all large enough multiples of $T$ in this, $f(a)$ takes the same values for all of these values, so $f(a) = 1$ on taking greatest common divisors. So, $f$ cycles back to $1$ eventually. Since the period is still T, take $a = T$, and we get that $f(b-1) \mid b^2$, so taking $b$ even, we get that $f(b) \mid b+1$. replacing $b$ with $b+T$ if $T$ is even and $b+2T$ if odd, we get that $f(b) \mid T$ if $T$ is even and $f(b) \mid 2T$ if $T$ is odd. In the former case, we must have $\tau(T) \geq T$, i.e. $T = 2$ and in the latter $\tau(2T) \geq T$, which is possible if $T = 1$ or $T = 3$. If $T = 3$, then since we earlier had that $f(a) \mid a^2-1$ and $f(a) \mid (a+1)^2$, analysing the latter shows that $f(a) = 1$ if $3$ does not divide $a+1$, which shows that $f$ has a smaller cycle. So, $T = 2$ or $T = 1$. Clearly $T = 1$ implies $f \equiv 1$. If $T = 2$ then note that $f(1) \mid 4$, and we can check that this implies we are done. Now, $f$ is injective, so, $f(f(a)) = f(f^a(1)) = f^{a+1}(1) = f(a+1)$, so $f(a) = a+1$ for all $a$.