Weird Functional Equation

Let $P(a, b)$ denote the assertion $f^{f(a)}(b) f^{f(b)}(a) = f(a + b)^2$ for all positive integers $a$ and $b$ .

$P(a, a)$ gives $f^{f(a)}(a) = f(2a)$ , or $f^{f(a) - 1}(a) = 2a$ since $f$ is injective.

Suppose there existed a $k$ with $f(k) = 1$ . Then, $P(k, k)$ gives $f^0(k) = 2k$ , i.e. $k = 2k$ , which is impossible. Thus, $f(a) \ge 2$ for all $a$ , so $f\left(f^{f(a) - 2}(a) \right) = 2a$ for all $a$ . Thus, all even positive integers are in the range of $f$ .

For every positive integer $n$ , define $S_n = \{n, f(n), f(f(n)), \dots\}.$ Then, the result above gives that $2n \in S_n$ for all $n$ . By an easy induction, we see that $2^k n \in S_n$ for all $k \ge 0$ , so $S_n$ is infinite for all $n$ .

Suppose $n$ and $k > 0$ are such that $f^k(n) = n$ . Then, $S_n$ is finite, a contradiction to the above. Thus, $f^k(n) \neq n$ for all $n$ and $k > 0$ .

We know that there exists a positive integer $k$ with $f(k) = 2$ . Then, $f^{f(k) - 1}(k) = 2k$ , or $2k = f^{f(k) - 1}(k) = f^1(k) = 2$ , so $k = 1$ . Thus, $f(1) = 2$ .

---

Next, we show that $f(2) = 3$ and $f(3) = 4$ . We know that there exists an integer $a \ge 1$ with $f(a + 1) = 4$ . Then, $P(1, a)$ gives $f(f(a)) f^{f(a)}(1) = f(a + 1)^2 = 16.$ We know that $f(f(a)) \neq 1$ , and if $f(f(a)) = 2$ , then $f(a) = 1$ , a contradiction. Thus, $f(f(a)) \ge 4$ .

Similarly, $f^{f(a)}(1) \neq 1$ , and if $f^{f(a)}(1) = 2$ , then $f^{f(a) - 1}(1) = 1$ , so $f(a) = 1$ , a contradiction. Thus, $f^{f(a)}(1) \ge 4$ .

These two inequalities force $f(f(a)) = f^{f(a)}(1) = 4$ . Since $f(a + 1) = 4$ , we get $f(a) = a + 1$ . In addition, $f^{f(a)}(1) = 4$ , or $f^{f(a) - 1}(2) = 4$ . However, from $P(2, 2)$ , we get $f^{f(2) - 1}(2) = 4$ , so $f(a) = f(2)$ and $a = 2$ . Finally, $f(a) = a + 1$ , so $f(2) = 3$ . Thus, $f(2) = 3$ and $f(a + 1) = f(3) = 4$ .

---

Now, we prove that $f(n) = n + 1$ by induction on $n$ . The base cases $f(n) = n + 1$ for $n \le 3$ have been done above.

Suppose that $f(n) = n + 1$ for all $n \le 2k - 1$ , with $k \ge 2$ . We will show that $f(2k) = 2k + 1$ and $f(2k + 1) = 2k + 2$ .

Let $a \ge 1$ be an integer with $f(a + 1) = 2k + 2$ . Then, $P(1, a)$ gives $f(f(a)) f^{f(a)}(1) = f(a + 1)^2 = (2k + 2)^2.$

Suppose that $f(f(a)) = r \le 2k$ . Then $f(a) = r - 1$ and $a = r - 2$ , so $f^{f(a)}(1) = f^{r - 1}(1) = r$ , since $r - 1 \le 2k - 1$ . Then, $r^2 = (2k + 2)^2$ , so $r = 2k + 2$ , a contradiction. Thus, $f(f(a)) \ge 2k + 1$ . However, since $2k + 1 \nmid (2k + 2)^2$ , we have $f(f(a)) \ge 2k + 2$ .

Suppose that $f^{f(a)}(1) = r \le 2k$ . Then, since $f^{r - 1}(1) = r$ , we get $f(a) = r - 1$ , so $a = r - 2$ , and similarly to the above, we get $f(f(a)) = r$ and $r = 2k + 2$ , a contradiction. Thus, $f^{f(a)}(1) \ge 2k + 1$ , and since $2k + 1 \nmid (2k + 2)^2$ , we get $f^{f(a)}(1) \ge 2k + 2$ .

The above inequalities force $f(f(a)) = f^{f(a)}(1) = 2k + 2$ . Recall that $f(a + 1) = 2k + 2$ as well, so $f(a) = a + 1$ .

However, from $P(k + 1, k + 1)$ , we know that $f^{f(k + 1) - 1}(k + 1) = 2k + 2$ . Since $k + 1 \le 2k - 1$ (as $k \ge 2$ ), we see that $f(k + 1) = k + 2$ , so $f^{k + 1}(k + 1) = 2k + 2$ .

However, we see that $f^{k - 1}(k + 1) = f^{k - 2}(k + 2) = \dots = f(2k - 1) = 2k,$ so $2k + 2 = f^{k + 1}(k + 1) = f(f(2k))$ . Since $f(a + 1) = 2k + 2$ , we see that $f(2k) = a + 1$ . Since $f(a) = a + 1$ as well, we see that $a = 2k$ , so $f(2k) = 2k + 1$ and $f(2k + 1) = 2k + 2$ .

---

The induction is complete, so the only possible function is $f(n) = n + 1$ for all $n$ . Since this forces $f^{f(a)}(b) = f^{f(b)}(a) = f(a + b) = a + b + 1$ for all $a$ and $b$ , this function is valid.

Therefore, $f(2017)=2018$ , and this is the only value, so the answer is $S = 2018 \pmod{1000} \equiv18$ .