Find all functions $f: \mathbb{N}\to \mathbb{N}$ such that for all $m,n\in \mathbb{N}$: \[f(f(m)+f(n))=m+n.\]
Problem
Source:
Tags: function, induction, strong induction, Functional Equations
22.09.2007 19:44
First, suppose $ f(a) = f(b) = c$. Then $ m = n = a$ and $ m = n = b$ gives $ f(2c) = 2a = 2b$, so $ a = b$ and $ f$ is injective. Suppose we have $ f(a) = 0$. Then $ m = n = 0$ gives $ f(0) = 2a$. Now $ m = n = 0$ gives $ f(4a) = 0 = f(a)$. So $ a = 4a$ and $ a = 0$. Now plug $ m = n = 0$ in to get $ f(2f(0)) = 0$, so $ f(0) = 0$. Plug $ m = 0$ in to get $ f(f(n)) = n$. Then let $ m = f(m)$. We get $ f(m+f(n)) = f(m)+n$. This equation is solved here, and both of its solutions also work for this one.
22.09.2007 19:54
With $ \mathbb{N}$ we mean $ \{1,2,...\}$ so I'm afraid you can't use $ m = 0$ or $ n = 0$ here. There is a nice solution at http://www.kalva.demon.co.uk/short/soln/sh8819.html if you want.
22.09.2007 20:09
Oops. Sorry about that. Injectivity still holds though, so I'll continue from that. Consider any $ k\in\mathbb{N}$. Note that $ f(f(k)+f(k+2)) = f(2f(k+m))$, so $ f(k+2)-f(k+1) = f(k+1)-f(k)$. An easy induction allows us to conclude that $ f(2)-f(1) = f(k+1)-f(k)$ for all natural $ k$. Now suppose that $ a < b$ and $ f(a) > f(b)$. Consider $ f(b)-f(b-1)+f(b-1)-f(b-2)+\ldots+f(a+1)-f(a)$. This allows us to conclude that $ f(b)-f(a) = (b-a)(f(2)-f(1))$. This also means that $ f(2) < f(1)$. But now we can conclude that $ f(k+1) < f(k)$, and this contradicts the well-ordering principle. Thus, $ f$ is nondecreasing. Now we prove by strong induction that $ f(k) = k$. Start with the base case $ k = 1$. Notice that $ f(2f(1)) = 2$. If $ f(1) > 1$, then $ 2f(1) > 2$ contradicting $ f$ nondecreasing. So $ f(1) = 1$. Now suppose the hypothesis is true for $ k$. Let $ m = 1$ and $ n = k$, and we get $ f(k+1) = k+1$, completing the induction.
07.04.2009 12:24
Hello! I'm a beginner at functional equations, so I'd like to ask you if the following solution is true. First let $ a,b,c,d\in \mathbb{N}$ and we notice $ f\left(f\left(f\left(a\right) + f\left(b\right)\right) + f\left(f\left(c\right) + f\left(d\right)\right)\right) = f\left(a\right) + f\left(b\right) + f\left(c\right) + f\left(d\right)$, but $ f\left(f\left(a\right) + f\left(b\right)\right) = a + b$ and $ f\left(f\left(c\right) + f\left(d\right)\right) = c + d$ so $ f\left(a + b + c + d\right) = f\left(a\right) + f\left(b\right) + f\left(c\right) + f\left(d\right)$. Setting $ a = b = c = d$ we get $ f\left(4a\right) = 4f\left(a\right)$. Let's fix $ a + b + c + d$, $ a$ and $ b$. So $ f\left(a + b + c + d\right) - f\left(a\right) - f\left(b\right) = const$. Therefore $ f\left(c\right) + f\left(d\right) = const$ but also $ c + d = const$. So for any $ p,q,r,g\in \mathbb{N}$ from $ p + q = r + g$ follows $ f\left(p\right) + f\left(q\right) = f\left(r\right) + f\left(g\right)$. Now we have $ f\left(1\right) + f\left(7\right) = f\left(4\right) + f\left(4\right)$, but $ f\left(4\right) = 4f\left(1\right)$ hence $ f\left(7\right) = 7f\left(1\right)$. We know also $ f\left(7\right) = f\left(2\right) + f\left(2\right) + f\left(2\right) + f\left(1\right)$ and since $ f\left(7\right) = 7f\left(1\right)$ $ f\left(2\right) = 2f\left(1\right)$. Now we are going to prove by induction that $ f\left(n\right) = nf\left(1\right)$ for every $ n\in \mathbb{N}$. For $ n = 1$, obvious! Assume it's true for $ n = k$. We are going to prove that it's true for $ n = k + 1$. We have $ f\left(k\right) + f\left(3k + 1\right) = f\left(4k\right) + f\left(1\right)$. $ f\left(k\right) = kf\left(1\right)$, $ f\left(4k\right) = 4f\left(k\right) = 4kf\left(1\right)$, and we conclude $ f\left(3k + 1\right) = \left(3k + 1\right)f\left(1\right)$. Now $ f\left(3k + 1\right) + f\left(k + 1\right) = f\left(4k\right) + f\left(2\right)$ $ \Rightarrow$ $ f\left(k + 1\right) = \left(k + 1\right)f\left(1\right)$. So the induction is finished and we proved $ f\left(n\right) = nf\left(1\right)$ for every $ n\in \mathbb{N}$. Now we have $ f\left(f\left(m\right) + f\left(n\right)\right) = f\left(\left(m + n\right)f\left(1\right)\right) = \left(m + n\right)f^{2}\left(1\right)$. But $ f\left(f\left(m\right) + f\left(n\right)\right) = m + n$ therefore $ \left(m + n\right)f^{2}\left(1\right) = m + n$ hence $ f^{2}\left(1\right) = 1$ $ \Rightarrow$ $ f\left(1\right) = 1$. $ f\left(n\right) = nf\left(1\right)$ hence $ f\left(n\right) = n$ for every $ n\in \mathbb{N}$.
11.04.2009 07:35
I think this problem can be solve shorter.By the equation, we obtain f is monotone (which mean f(x)=f(y) if only if x=y) let n=m+2 we have f( f(m+2)+f(m) )=2m+2=f( 2 f(m+1)) because f is monotone we have f(2) - f(1)=f(3) - f(2)=.......=f(n+1) - f(n) = d = constant for all n in N and f(n) = (n-1)d + f(1)
22.05.2022 09:57
Lemma: $f$ is injective. Proof. If $f(m)=f(n),$ then $$m+k=f(f(m)+f(k))=f(f(n)+f(k))=n+k,$$implying the claim. $\blacksquare$ Setting $m=n+2,$ yields that $f(n+2)+f(n)=2f(n+1).$ By induction, $f(n+1)-f(n)$ is constant. Clearly $f$ is linear. If $f(n)=an+b,$ then plugging in the original yields $a=1$ and $b=0,$ hence the identity function works.