170128 함수방정식

미국 가는 비행기에서 친구와 푼 문제이다. 각자 발견한 아이디어를 합쳐보니 꽤 재밌는 풀이가 나와 포스팅해본다.

$$\text{ Find all function } f : \mathbb{N} \to \mathbb{N} \text{ s.t. } \\ \forall a,b\in \mathbb{N} (f(a)+b)\cdot f(a+f(b)) = (a+f(b))^2$$

(step 1)

$P(a,a) : f( \ a \ + f(a) \ ) = a+f(a)$

즉, $x + f(x)$꼴로 나타내어 지는 수들은 모두 부동점이다.

$f$의 부동점들의 집합을 $A$라고 하자.

그렇다면 $x,y\in A$에 대해 $x+y \in A$임을 쉽게 보일 수 있다. $\cdots (*)$

(step 2)

$a+f(a)$는 부동점이므로 이를 활용해 보자.

$P(a, a+f(a)) : f(2a+f(a)) = \frac{[2a+f(a)]^2}{a+2f(a)}$

따라서 $a + 2f(a) | (2a+f(a))^2$이고, 식을 정리하면 $a + 2f(a) | 9a^2$이다.

따라서 a에 1을 대입하면 $1+2f(1) | 9$이고, 이로부터 $f(1) = 1 \vee 4$이다.

(step 3)

$f(1) = 1$인 경우, 재귀적으로 모든 $k\in \mathbb{N}$에 대해 $f(2^k) = 2^k$임을 보일 수 있다. 이 때 모든 수는 이진법으로 나타낼 수 있으므로, $(*)$에 의해 $f(x) = x$가 되고, 이는 주어진 함수방정식을 만족한다.

(step 4)

$f(1) = 4$인 경우, 마찬가지로 모든 $k \in \mathbb{N}$ 에 대해 $f(5 \cdot 2^k) = 5 \cdot 2^k$임을 알 수 있다. 즉, $A$는 무한집합이다.

이 때, 적당한 $A$의 원소 $p$를 잡자.

$P(p,1) : (p+1)\cdot f(p+4) = (p+4)^2$

이 때 $p+1 | (p+4)^2 \Rightarrow p+1 | 9$인데, $p$의 값이 8보다 커지면 모순. 따라서 조건을 만족하는 해는 $f(x) = x$ 뿐이다. $\blacksquare$