Let S be the set of non-negative integers. Find all functions f: S→S such that f(m + f(n)) = f(f(m)) + f(n) for all m, n.
Solution
Setting m = n = 0, the given relation becomes: f(f(0)) = f(f(0)) + f(0). Hence f(0) = 0. Hence also f(f(0)) = 0. Setting m = 0, now gives f(f(n)) = f(n), so we may write the original relation as f(m + f(n)) = f(m) + f(n).
So f(n) is a fixed point. Let k be the smallest non-zero fixed point. If k does not exist, then f(n) is zero for all n, which is a possible solution. If k does exist, then an easy induction shows that f(qk) = qk for all non-negative integers q. Now if n is another fixed point, write n = kq + r, with 0 ≤ r < k. Then f(n) = f(r + f(kq)) = f(r) + f(kq) = kq + f(r). Hence f(r) = r, so r must be zero. Hence the fixed points are precisely the multiples of k.
But f(n) is a fixed point for any n, so f(n) is a multiple of k for any n. Let us take n1, n2, ... , nk-1 to be arbitrary non-negative integers and set n0 = 0. Then the most general function satisfying the conditions we have established so far is:
f(qk + r) = qk + nrk for 0 ≤ r < k.
We can check that this satisfies the functional equation. Let m = ak + r, n = bk + s, with 0 ≤ r, s < k. Then f(f(m)) = f(m) = ak + nrk, and f(n) = bk + nsk, so f(m + f(n)) = ak + bk + nrk + nsk, and f(f(m)) + f(n) = ak + bk + nrk + nsk. So this is a solution and hence the most general solution.
© John Scholes
jscholes@kalva.demon.co.uk
22 Oct 1998
Last corrected/updated 21 Aug 03