Let $ f :\mathbb N \to \mathbb N $ be an injective function such that $$ f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ( a + b ) ^ 2 $$ for all $ a , b \in \mathbb N $. Let $ S $ be the sum of all possible values of $ f ( 2017 ) $. Find $ S \bmod 1000 $. Here $$ f ^ k ( n ) = \underbrace { f \Big( \dots f \big( f } _ { k \text{ times} } ( n ) \big) \dots \Big) \text . $$
So I put $ a = b $ and found out that $ f ^ { f ( a ) } ( a ) = f ( 2 a ) $.
Since $ f $ is injective, $ f ^ { f ( a ) - 1 } ( a ) = 2 a $. I found out that $ f ( 1 ) = 2 $.
Now $ f ( 2 ) = 3 $ by putting value of $ a = 1 $ in initial equation and solving for $ f ( b ) = 3 $. It seems by guessing that $ f ( n ) = n + 1 $ but can't the function be periodic after certain interval and is unbounded and repeat its value? It can still be injective.
It's easy to see that $ f ( n ) = n + 1 $ satisfies the functional equation $$ f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ( a + b ) ^ 2 \text , \tag 0 \label 0 $$ since then for every positive integers $ m $ and $ n $, one will have $ f ^ m ( n ) = n + m $. It can be shown that this is the only injective solution to \eqref{0} that maps positive integers to positive integers, and thus the only possible value for $ f ( 2017 ) $ is $ 2018 $, which shows $ S = 2018 $ and hence $ S \bmod 1000 = 18 $. To see this, first note that $ f $ cannot take the value $ 1 $, because if $ f ( n ) = 1 $ for some positive integer $ n $, then letting $ a = b = n $ in \eqref{0}, you get $ f ( 2 n ) = 1 $, which by injectivity of $ f $ yields $ n = 2 n $, which can't happen. Next, let $ b = a $ in \eqref{0} to get $$ f ^ { f ( a ) } ( a ) = f ( 2 a ) \text , $$ and by injectivity, $$ f ^ { f ( a ) - 1 } ( a ) = 2 a \text , \tag 1 \label 1 $$ as you've done yourself. We can use \eqref{1} to inductively prove $$ f ^ { \sum _ { m = 1 } ^ n f \left( 2 ^ { m - 1 } a \right) - n } ( a ) = 2 ^ n a $$ for every nonnegative integer $ n $ (note that if $ n = 0 $, the left-hand side gives $ f ^ 0 ( a ) $ that means $ a $ itself), which in particular shows that $ \left\{ f ^ i ( a ) \right\} _ { i = 0 } ^ \infty $ is infinite. As a consequence, we can see that if for some nonnegative integers $ i $ and $ j $ we have $ f ^ i ( a ) = f ^ j ( a ) $, then we must have $ i = j $.
We can now show that $ f ( 1 ) = 2 $. If that's not the case, we must have $ f ( 1 ) = n + 2 $ for some positive integer $ n $. Then we have $ f ^ { n + 1 } ( 1 ) = 2 $ by putting $ a = 1 $ in \eqref{1}, and letting $ a = f ^ n ( 1 ) $ in \eqref{1} we get $$ 2 f ^ n ( 1 ) = f ^ { f \left( f ^ n ( 1 ) \right) - 1 } \big( f ^ n ( 1 ) \big) = f ^ { f ^ { n + 1 } ( 1 ) - 1 } \big( f ^ n ( 1 ) \big) = f ^ { 2 - 1 } \big( f ^ n ( 1 ) \big) = f ^ { n + 1 } ( 1 ) = 2 \text . $$ But this means $ f \left( f ^ { n - 1 } ( 1 ) \right) = 1 $, which is impossible.
Then, we show that $ f ( 2 ) = 3 $. To see this, first note that if for some positive integer $ n $ and some positive integer $ k \ne 1 $ we have $ f ( n ) = 2 k $, letting $ a = k $ in \eqref{1} we get $ f ^ { f ( k ) - 1 } ( k ) = f ( n ) $, and as we must have $ f ( k ) > 2 $, we get $ f \left( f ^ { f ( k ) - 3 } ( k ) \right) = f ( n ) $. By injectivity of $ f $, we conclude that there is a positive integer $ m $ such that $ f ( m ) = n $. Since by putting $ a = 1 $ and $ b = 2 $ in \eqref{0} and using \eqref{1} we have $$ f ( 3 ) ^ 2 = f ^ { f ( 1 ) } ( 2 ) f ^ { f ( 2 ) } ( 1 ) = f ^ 2 ( 2 ) f ^ { f ( 2 ) - 1 } \big( f ( 1 ) \big) = f ^ 2 ( 2 ) f ^ { f ( 2 ) - 1 } ( 2 ) = 4 f ^ 2 ( 2 ) \text , $$ it follows that there is a positive integer $ k $ such that $ f ( 3 ) = 2 k $. As $ f ( 3 ) \ne f ( 1 ) = 2 $, we must have $ k \ne 1 $, and thus there is a positive integer $ m $ with $ f ( m ) = 3 $. We know that $ m \ne 1 $. $ m $ cannot be equal to $ 3 $ either, because then by \eqref{1} we would have $ 6 = f ^ { f ( 3 ) - 1 } ( 3 ) = f ^ 2 ( 3 ) = 3 $. If $ m > 3 $, we can let $ a = m - 3 $ and $ b = 3 $ in \eqref{0} and see that $$ 9 = f ( m ) ^ 2 = f ^ { f ( m - 3 ) } ( 3 ) f ^ { f ( 3 ) } ( m - 3 ) \text . $$ As non of $ f ^ { f ( m - 3 ) } ( 3 ) $ and $ f ^ { f ( 3 ) } ( m - 3 ) $ can be equal to $ 1 $, we must have $ f ^ { f ( m - 3 ) } ( 3 ) = f ^ { f ( 3 ) } ( m - 3 ) = 3 $. But $ f ^ { f ( m - 3 ) } ( 3 ) = 3 = f ^ 0 ( 3 ) $ leads to $ f ( m - 3 ) = 0 $, which is impossible. Thus the only possible case is $ m = 2 $, as desired.
At last, we use strong induction on $ n $ to prove that $ f ( n ) = n + 1 $ for every positive integer $ n \ge 3 $. Note that as $ n \ge 3 $, if we let $ a = \left\lfloor \frac { n + 1 } 2 \right\rfloor $ and $ b = \left\lceil \frac { n + 1 } 2 \right\rceil $, then $ a $ and $ b $ are positive integers less than $ n $ such that $ a + b = n + 1 $. By induction hypothesis, assume that $ f ( m ) = m + 1 $ for every positive integer $ m $ less than $ n $. This shows that $ f ^ { n - m } ( m ) = n $ for every positive integer $ m $ less than $ n $. Thus, using \eqref{0} we have $$ f ( n + 1 ) ^ 2 = f ( a + b ) ^ 2 = f ^ { f ( a ) } ( b ) f ^ { f ( b ) } ( a ) = f ^ { a + 1 } ( b ) f ^ { b + 1 } ( a ) \\ = f ^ { n + 2 - b } ( b ) f ^ { n + 2 - a } ( a ) = f ^ 2 \left( f ^ { n - b } ( b ) \right) f ^ 2 \left( f ^ { n - a } ( a ) \right) = \left( f ^ 2 ( n ) \right) ^ 2 \text . $$ Therefore we have $ f ( n + 1 ) = f \big( f ( n ) \big) $, and hence by injectivity of $ f $, $ f ( n ) = n + 1 $, as desired.