**Step 1. ($f$ is injective)
Claim 1.** For any $a \ge 2$, the set $\{f^n(a) \mid n \in \mathbb{Z}_{\ge 0}\}$ is infinite.
Proof. First, we have $f^{f(a)}(a+1) \stackrel{P(a,1)}{=} (a+1)f(1)$. Varying $a$, we see that $f(\mathbb{Z}_{\ge 0})$ is infinite. Next, we have $f^{bf(a-1)}(a) \stackrel{P(a-1,b)}{=} af(b)$. So, varying $b$, $f^{bf(a-1)}(a)$ takes infinitely many values. $\square$
Claim 2. For any $a \ge 2$ and $n \in \mathbb{Z}_{\ge 0}$, we have $f^n(a) \ne a$.
Proof. Otherwise, we would get a contradiction with Claim 1. $\square$
Assume $f(b) = f(c)$ for some $b < c$. Then we have
$$\begin{align*} (a+1)f(c) &\stackrel{P(a,c)}{=} f^{cf(a)}(a+1) \\ &= f^{(c-b)f(a)}(f^{bf(a)}(a+1)) \\ &\stackrel{P(a,b)}{=} f^{(c-b)f(a)}((a+1)f(b)) \\ &= f^{(c-b)f(a)}((a+1)f(c)), \end{align*}$$
which contradicts Claim 2. So, $f$ is injective.

Step 2. ($f(\mathbb{Z}_{>0}) = \mathbb{Z}_{\ge 2}$)
Claim 3. $1$ is not in the range of $f$.
Proof. If $f(b) = 1$, then $f^{f(a)}(a+1) = a+1$ by $P(a, 1)$, which contradicts Claim 2. $\square$
We say that $a$ is a descendant of $b$ if $f^n(b) = a$ for some $n \in \mathbb{Z}_{>0}$.
Claim 4 For any $a, b \ge 1$, both of the following cannot happen at the same time:
- $a$ is a descendant of $b$;
- $b$ is a descendant of $a$.
Proof. If both of the above hold, then $a = f^m(b)$ and $b = f^n(a)$ for some $m, n \in \mathbb{Z}_{>0}$. Then $a = f^{m+n}(a)$, which contradicts Claim 2. $\square$
Claim 5 For any $a, b \ge 2$, exactly one of the following holds:
- $a$ is a descendant of $b$;
- $b$ is a descendant of $a$;
- $a = b$.
Proof. For any $c \ge 2$, taking $m = f^{cf(a-1)-1}(a)$ and $n = f^{cf(b-1)-1}(b)$, we have
$$f(m) = f^{cf(a-1)-1}(a) \stackrel{P(a-1,c)}{=} af(c) \quad \text{and} \quad f(n) = f^{cf(b-1)-1}(b) \stackrel{P(b-1,c)}{=} bf(c).$$
Hence
$$f^{nf(a-1)}(a) \stackrel{P(a-1,n)}{=} af(n) = abf(c) = bf(m) \stackrel{P(a-1,m)}{=} f^{mf(b-1)}(b).$$
The assertion then follows from the injectivity of $f$ and Claim 2. $\square$
Now, we show that any $a \ge 2$ is in the range of $f$. Let $b = f(1)$. If $a = b$, then $a$ is in the range of $f$. If $a \ne b$, either $a$ is a descendant of $b$, or $b$ is a descendant of $a$ by Claim 5. If $b$ is a descendant of $a$, then $b = f^n(a)$ for some $n \in \mathbb{Z}_{>0}$, so $1 = f^{n-1}(a)$. Then, by Claim 3, we have $n = 1$, so $1 = a$, which is absurd. So, $a$ is a descendant of $b$. In particular, $a$ is in the range of $f$. Thus, $f(\mathbb{Z}_{>0}) = \mathbb{Z}_{\ge 2}$.

Step 3. ($f(1) = 2$)
Claim 6 Let $a, n \ge 2$, then $na$ is a descendant of $a$.
Proof. We write $n = f(m)$ by Step 2. We have $na = f(m)a \stackrel{P(a-1,m)}{=} f^{mf(a-1)}(a)$, which shows $na$ is a descendant of $a$. $\square$
By Claim 6, all even integers $\ge 4$ are descendants of 2. Hence $2 = f(2k + 1)$ for some $k \ge 0$. Next, we show $f(2k+1) \ge f(1)$, which implies $f(1) = 2$. It trivially holds if $k = 0$. If $k \ge 1$, let $n$ be the integer such that $f^n(2) = 2k + 2$. For any $b > n/f(1)$, we have
$$f^{bf(1)-n}(2k+2) = f^{bf(1)}(2) \stackrel{P(1,b)}{=} 2f(b) \quad \text{and} \quad f^{bf(2k+1)}(2k+2) \stackrel{P(2k+1,b)}{=} (2k+2)f(b).$$
By Claim 6, $(2k+2)f(b)$ is a descendant of $2f(b)$. By Claim 2, we have $b(2k+1) > bf(1) - n$. By taking $b$ large enough, we conclude $f(2k+1) \ge f(1)$.

Step 4. ($f(2) = 3$ and $f(3) = 4$)
From $f(1) = 2$ and $P(1,b)$, we have $f^{2b}(2) = 2f(b)$. So taking $b=1$, we obtain $f^2(2) = 2f(1) = 4$; and taking $b = f(2)$, we have $f^{2f(2)}(2) = 2f^2(2) = 8$. Hence, $f^{2f(2)-2}(4) = f^{2f(2)}(2) = 8$ and $f^3(4) \stackrel{P(3,1)}{=} 8$ give $f(3) = 2f(2) - 2$.
Claim 7 For any $m, n \in \mathbb{Z}_{>0}$, if $f(m)$ divides $f(n)$, then $m \le n$.
Proof. If $f(m) = f(n)$, the assertion follows from the injectivity of $f$. If $f(m) < f(n)$, by $P(a,m)$, $P(a,n)$ and Claim 6, we have that $f^{nf(a)}(a+1)$ is a descendant of $f^{mf(a)}(a+1)$ for any $a \in \mathbb{Z}_{>0}$. So $mf(a) < nf(a)$, and $m < n$. $\square$
By Claim 7, every possible divisor of $f(2)$ is in $\{1, f(1) = 2, f(2)\}$. Thus $f(2)$ is an odd prime or $f(2) = 4$. Since $f^2(2) = 4$, we have $f(2) \ne 4$, and hence $f(2)$ is an odd prime. We set $p = f(2)$.
Now, $f(3) = 2f(2) - 2 = 2(p-1)$. Since $p-1$ divides $f(3)$, we have $p-1 \in \{1, f(1) = 2, f(2) = p\}$ by Claim 7, so $p-1 = 2$. Thus, $f(2) = p = 3$ and $f(3) = 2(p-1) = 4$.

Step 5. ($f(n) = n + 1$)
Claim 8 For any $b \ge 1$, $f(2f(b) - 1) = 2b + 2$.
Proof. Since $f^2(2) = 4$, we have $f^{2b-2}(4) = f^{2b}(2) = 2f(b)$, so
$$f^{f(2f(b)-1)+2b-2}(4) = f^{f(2f(b)-1)}(2f(b)) \stackrel{P(2f(b)-1,1)}{=} 4f(b) \stackrel{P(3,b)}{=} f^{4b}(4),$$
which gives us $f(2f(b) - 1) = 2b + 2$. $\square$
Finally, we prove $f(n) = n + 1$ by induction on $n$. Suppose $f(n) = n + 1$ for all $1 \le n \le 2b + 1$. Replace $b$ by $b + 1$ in $f(2f(b) - 1) = 2b + 2$ to get
$$f(2b + 3) = f(2f(b + 1) - 1) = 2(b + 1) + 2 = 2b + 4.$$
By induction hypothesis, we have $f^b(b + 2) = 2b + 2$. Hence
$$f(f(2b + 2)) = f^{b+2}(b + 2) = f^{f(b+1)}(b + 2) \stackrel{P(b+1,1)}{=} 2(b + 2) = f(2b + 3).$$
By injectivity, $f(2b + 2) = 2b + 3$. Then $f(n) = n + 1$ for all $n \in \mathbb{Z}_{\ge 0}$, which is indeed a solution.

In the same way as Steps 1-2 of Solution 1, we have that $f$ is injective and $f(\mathbb{Z}_{>0}) = \mathbb{Z}_{\ge 2}$.
We first note that Claim 2 in Solution 1 is also true for $a = 1$.
Claim 2' For any $a, n \in \mathbb{Z}_{>0}$, we have $f^n(a) \ne a$.
Proof. If $a \ge 2$, the assertion was proved in Claim 2 in Solution 1. If $a = 1$, we have that 1 is not in the range of $f$ by Claim 3 in Solution 1. So, $f^n(1) \ne 1$ for every $n \in \mathbb{Z}_{\ge 0}$. $\square$
For any $a, b \in \mathbb{Z}_{>0}$, we have
$$f^{bf(f(a)-1)+1}(a) = f^{bf(f(a)-1)+1}(f(a)) \stackrel{P(f(a)-1,b)}{=} f(a)f(b).$$
Since the right-hand side is symmetric in $a, b$, we have
$$f^{bf(f(a)-1)+1}(a) = f(a)f(b) = f^{af(f(b)-1)+1}(b)$$
Since $f$ is injective, we have $f^{bf(f(a)-1)}(a) = f(a)f(b) = f^{af(f(b)-1)}(b)$. We set $g(n) = f(f(n) - 1)$. Then we have $f^{bg(a)}(a) = f^{ag(b)}(b)$ for any $a, b \in \mathbb{Z}_{\ge 0}$. We set $n_{a,b} = bg(a) - ag(b)$. Then, for sufficiently large $n$, we have $f^{n+n_{a,b}}(a) = f^n(b)$. For any $a, b, c \in \mathbb{Z}_{>0}$ and sufficiently large $n$, we have
$$f^{n+n_{a,b}+n_{b,c}+n_{c,a}}(a) = f^n(a).$$
By Claim 2' above, we have $n_{a,b} + n_{b,c} + n_{c,a} = 0$, so
$$(a - b)g(c) + (b - c)g(a) + (c - a)g(b) = 0.$$
Taking $(a, b, c) = (n, n+1, n+2)$, we have $g(n+1) - g(n) = g(n+2) - g(n+1)$. So, $\{g(n)\}_{n \ge 1}$ is an arithmetic progression.
There exist $C, D \in \mathbb{Z}$ such that $g(n) = f(f(n) - 1) = Cn + D$ for all $n \in \mathbb{Z}_{>0}$. By Step 2 of Solution 1, we have $f(\mathbb{Z}_{>0}) = \mathbb{Z}_{\ge 2}$, So $C = 1$. Since $2 = \min_{n \in \mathbb{Z}_{>0}} \{f(f(n) - 1)\}$, we have $D = 1$.
Thus, $g(n) = f(f(n) - 1) = n + 1$ for all $n \ge 1$. For any $a, b \in \mathbb{Z}_{>0}$ taking $(a, b) = (1, n)$, we have $f^n(1) = f(n)$, $f^{n-1}(1) = n$ again by the injectivity of $f$. For any $n \ge 1$, we have $f(n) = f(f^{n-1}(1)) = f^n(1) = n + 1$.