Find all functions $f : \mathbb{Z} \to \mathbb{Z}$ that satisfy the conditions: $i) f(f(x)) = xf(x) - x^2 + 2,\forall x\in\mathbb{Z}$ $ii) f$ takes all integer values
Problem
Source: Peru Ibero+Cono Sur TST 2020 P2
Tags: number theory, functional equation
12.09.2023 21:19
Let $P(x)$ be the assertion. Say $f(1)=\beta$ for some integer $\beta$ Then from $P(1)$ you get $f(\beta)=\beta+1$ for that some integer $\beta$. $\textcolor{red}{Claim:}$ For any integer $a\geq0$ we have $f(\beta+a)=\beta+a+1.$ $\textcolor{red}{Proof:}$ From $P(\beta)$ you get $f(\beta+1)=\beta+2\implies f(\beta+2)=\beta+3\implies...\implies f(\beta+a)=\beta+a+1$. Thus our proof is complete. $\textcolor{red}{Claim:}$ $f$ is injective. $\textcolor{red}{Proof:}$ Assume $f(x)=f(y)$ for some integer $x\neq y.$ Then we have $f(f(x))=f(f(y))=xf(x)-x^{2}+2=yf(x)-y^{2}+2$ thus $f(x)=f(y)=x+y.$ Now we have $f(\beta-1)=f(1)=\beta$ and, $f(\beta)=f(1)=\beta+1$ meaning $\beta=\beta+1$ a contradiction. $\textcolor{red}{Claim:}$ $f$ is strictly increasing. $\textcolor{red}{Proof:}$ if f is increasing than we have $f(x+1)\geq f(x)+1$. Now $f(f(x+1))>f(f(x))\implies (x+1)f(x+1)-(x+1)^{2}>f(x)x-x^{2}$ Since $(x+1)f(x+1)-(x+1)^{2}\geq(x+1)(f(x)-x)$ we have $(x+1)(f(x)-x)>(x)(f(x)-x)$. If $f(x)=x$ then we have x=2 from $P(x)$. Now since $f(f(0))=2$ we have $f(0)=2$ but because the function is injective this is not true. The function is always strictly increasing. $\textcolor{green}{Case 1:}$ $\beta\leq1$ From $P(0)$ we have $f(f(0))=2$. Since $f(x+1)=f(x)+1$ for every $x\in[\beta<\infty]$ we have $f(2)=f(1)+1$.From $P(f(0))$ We have $f(2)=2f(0)-f^{2}(0)+2=f(1)+1.$ Thus $\left(f(0)-1)\right)^{2}+f(1)=2.$ Since $f(x)\in\mathbb{Z},$ and $f(1)\leq1$ we are left with 2 cases: $\textcolor{blue}{Subcase 1.1:}$$f(0)=0$ Since $f(0)=2$ from $P(0)$ we have $f(0)=2=0$ a contradiction. $\textcolor{blue}{Subcase 1.2:}$ $f(0)=2$ Since $f$ is surjective say $f(z)=0$ for some integer z. Then from $P(f(0))$ we have $f(0)=2-z^{2}=2.$ Thus $z=0$ now we have $f(0)=2=0$ a contradiction. We have no solutions in this case. $\textcolor{green}{Case 2:}$ $\beta\geq 2$ From $P(f(f(0)))$ we have $f(2)=-(f(0)-1)^{2}+3$ Since $f(1)<f(2)$ we have $2\leq\beta<3-(f(0)-1)^{2}$ Thus $(f(0)-1)\leq0$ and $f(0)=1.$ From this we know that $f(2)=3,$ $\beta=2,.$$f(-1)=0.$ From induction $\boxed{f(x)=x+1}.$
12.09.2023 22:02
Quote: Since $f$ is strictly increasing in $[\beta,\infty]$ we have $f(2)=f(1)+1$. You will have to convince me of this.
12.09.2023 22:59
Let $P(x)$ be the assertion that $f(f(x)) = xf(x) - x^2 + 2$ Let $f(1) = b, f(v) = 1$ (all fine because $f$ is surjective) $P(1)\implies f(b) = b+1$ By induction, $P(b+n)\implies f(b+n) = b+n+1 \quad\forall n>0$ $P(v)\implies b=2, v=0$ (some trivial case-work to come to this conclusion) Thus $f(x) = x+1$ for all non-negative integers. Claim: $f(-n) = 1-n$ for all $n\ge0$.
Thus $\boxed{f(x) = x+1\quad\forall x\in\mathbb Z}$
13.09.2023 18:23
Belarus TST 2019