hajimbrak wrote: Find all functions $f : \mathbb{Z} \to\mathbb{ Z}$ such that $$n^2+4f(n)=f(f(n))^2$$ for all $n\in \mathbb{Z}$. Here is an ugly heavy solution (hope somebody will find something prettier) : Let $P(n)$ be the assertion $n^2+4f(n)=f(f(n))^2$ Let $a=f(0)$ Note that $f(u)=f(v)$ implies $u=\pm v$ Equation immediately implies that $\forall n$, either $f(n)=0$, either $|f(n)|\ge |n|-1$ and $|f(n)|\ge |f(f(n))|-1$ Replacing $n$ by $f(n)$, we also get that $\forall n$, either $f(f(n))=0$, either $|f(f(n))|\ge |f(n)|-1$ So $\forall n$, if $f(n)\ne 0$ and $f(f(n))\ne 0$, we get $|f(n)|+1\ge |f(f(n))|\ge |f(n)|-1$ So $\forall n$ : either $f(n)=0$, either $|f(f(n))|\in\{0,|f(n)|-1,|f(n)|,|f(n)+1\}$ If $f(n)=0$, equation implies $n=\pm a$ If $f(n)\ne 0$ and $|f(f(n))|=|f(n)|$, equation implies $n^2+4=(f(n)-2)^2$ and so $n=0$ and $f(0)=4$ and $f(4)=-4$ (since $f(4)=f(0)=4$ is impossible) and then $P(4)$ implies $f(-4)=0$ If $f(n)\ne 0$ and $|f(f(n))|=|f(n)|-1$, equation implies $n^2+4f(n)=f(n)^2-2|f(n)|+1$ and so : - either $f(n)<0$ and $f(n)=1-|n|$ - either $f(n)>0$ and $n^2+8=(f(n)-3)^2$ and so $n=\pm 1$ and $f(n)=6$ If $f(n)\ne 0$ and $|f(f(n))|=|f(n)|+1$, equation implies $n^2+4f(n)=f(n)^2+2|f(n)|+1$ and so : - either $f(n)>0$ and $f(n)=1+|n|$ - either $f(n)<0$ and $n^2+8=(f(n)-3)^2$ and so $n=\pm 1$ and $f(n)=\in\{0,6\}$, impossible As a intermediate conclusion, we get that $\forall n\notin\{-1,0,1\}$, $f(n)\in\{0,1+n,1-n\}$ This forbids the case $f(4)=-4$ Let us have a look at the case $f(n)=0$ : If $f(u)=0$, then $P(u)$ implies $f(0)=\pm u$ and since $P(0)$ implies $f(0)\ge 0$, we get $f(0)=|u|$ $P(0)$ $\implies$ $f(|u|)^2=4|u|$ and so : If $u\ge 0$, this becomes $f(u)^2=4u$ and so $u=0$ If $u<0$, this implies $u=-t^2$ for some $t\ge 1$ and so : $f(-t^2)=0$ and $f(t^2)=\pm 2t$ and $f(0)=t^2$ and then $P(t^2)$ implies $t^4\pm 8t$ perfect square and so $t\in\{1,2\}$ but we previously got that the case $t=2$ did not match And so $f(n)=0$ implies $n\in\{0,-1\}$ So $\forall n\notin\{-1,0,1\}$, $f(n)\in\{1+n,1-n\}$ So $f(2)\in\{-1,3\}$ If $f(2)=-1$ : $P(2)$ $\implies$ $f(-1)=0$ $P(-1)$ $\implies$ $f(0)=1$ (remember that $P(0)$ implies $f(0)\ge 0$) $P(0)$ $\implies$ $f(1)=\pm 2$ but then $P(1)$ is wrong. So $f(2)=3$ and simple induction implies $f(n)=n+1$ $\forall n\ge 2$ If $f(k)=1+k$ for some $k<-1$, it is easy to show with induction that $f(n)=n+1$ $\forall$ $n\in[k,-2]$ Then $P(-2)$ implies $f(-1)=0$ $P(-1)$ implies $f(0)=1$ (since $\ge 0$) $P(0)$ implies $f(1)=\pm 2$ and $P(1)$ implies $f(1)=2$ If $f(n)=1-n$ $\forall n<-1$ $P(-1)$ implies $f(-1)\in\{0,2\}$ If $f(-1)=0$ we easily get $f(0)=1$ and $f(1)=2$ If $f(-1)=2$ : $P(1)$ implies $f(1)\in\{0,2\}$ and so $f(1)=2$ and then $f(0)\in\{0,1\}$ Hence all the solutions : $\boxed{\text{S1 : }f(x)=1+x\text{ }\forall x\in\mathbb Z}$ which indeed is a solution $\boxed{\text{S2 : }f(x)=1-x\text{ }\forall x\le a\text{ and }f(x)=1+x\text{ }\forall x> a}$ which indeed is a solution, whatever is integer $a\le 0$ $\boxed{\text{S3 : }f(0)=0\text{ and }f(x)=1-x\text{ }\forall x<0\text{ and }f(x)=1+x\text{ }\forall x>0}$ which indeed is a solution

The official solution is just bash -_-

pco wrote: hajimbrak wrote: Find all functions $f : \mathbb{Z} \to\mathbb{ Z}$ such that $$n^2+4f(n)=f(f(n))^2$$ for all $n\in \mathbb{Z}$. Here is an ugly heavy solution (hope somebody will find something prettier) : If you had seen the official solution, you would have been really happy with your beautiful solution.

can anyone explain me why $|f(n)|\ge |n|-1$ and $|f(n)|\ge |f(f(n))|-1$ thank

jindoak10 wrote: can anyone explain me why $|f(n)|\ge |n|-1$ and $|f(n)|\ge |f(f(n))|-1$ thank If you have $a^2+4b=c^2$ where $a,b,c\in\mathbb Z$, then : Either $b=0$ Either $b>0$ and so $|c|\ge |a|+2$ (they are both odd or both even) and so $4b\ge 4|a|+4$ and so $b\ge |a|+1\ge |a|-1$ Either $b<0$ and so $|a|\ge 2$ and $|c|\le |a|-2$ (they are both odd or both even) and so $4b\le -4|a|+4$ and so $-b\ge |a|-1$ And so either $b=0$, either $|b|\ge |a|-1$ But we may also write $a^2+4b=c^2$ as $c^2+4(-b)=a^2$ and same path gives : either $b=0$, either $|b|\ge |c|-1$ So $a^2+4b=c^2$ implies either $b=0$, either $|b|\ge |a|-1$ and $|b|\ge |c|-1$

Pco thank you a lot

Can someone explain how $f(u)=f(v)$ implies $u=\pm v$

Plops wrote: Can someone explain how $f(u)=f(v)$ implies $u=\pm v$ Because $f(u)=f(v)$ implies $u^2=f(f(u))^2-4f(u)=f(f(v))^2-4f(v)=v^2$

What a Pathological problem. Here is a (long) solution with ewan. The solution set consists of three families: 1. $f(x) \equiv x+1$. 2. $$f(x) = \begin{cases} x+1 & x \geq C \\ 1-x & x < C\\ \end{cases}$$ for some $C \leq 0$. 3. $$f(x) = \begin{cases} x+1 & x > 0\\ 0 & x = 0 \\ 1-x & x < 0\\ \end{cases}.$$ We break the solution into multiple parts. First is a useful lemma: Lemma 1: Consider the functional digraph of $f$. The only cycles that appears in it, if any, are $0\to 0$ or $4\to -4\to 0\to 4$ (obviously not both)

Lemma 2: If $f(a) = 0$, then $a\in \{-4, -1, 0\}$.

Lemma 3: For all $n$, $|f(n)| \geq |n|-1$ unless $n = -4$ and $f(-4) = 0$.

Lemma 4: For $|n| > 4$, $f(n) \in \{1-n, 1+n\}$. Furthermore, if $f(n) \neq 0, f(f(n))\neq 0$, and $|n| > 1$, then $f(n) \in \{1-n, 1+n\}$.

Lemma 5: For $n \geq 1$, $f(n) = n+1$.

Lemma 6: The only cycle possible is $0\to 0$ and if $f(a) = 0$, then $a\in \{-1, 0\}$.

Lemma 7: For $n < 0$, if $f(n) = n+1$, then $f(n+1) = n+2$.

Lemma 8: For all $n \neq 0$, $f(n) \in \{1-n, 1+n\}$. Also, $f(0) \in \{0, 1\}$.

Lemma 9: If $f(0) = 0$, we obtain family 3.

Lemma 10: If $f(0) = 1$, we obtain families 1 and 2.

Thus we have obtained the desired families of solutions.

Solution with awang11 and stroller. For fun, we shall provide a series of 9 claims that will give the solution easily. And of course, we shall appreciate the pure bashiness of the problem by letting all claims to be exposed fully. No hide tags! Claim 1. For any chain $a_0=n,a_1=f(n),\ldots$, we have $$a_{n-2}^2+4a_{n-1}=a_n^2$$ Proof. Just use the functional equation and substitute into the recurrence. This is quite literally from the definition. Claim 2. $f(m)=f(n)\implies m=\pm n$. Proof. Substituting $m$ and $n$, we get $$m^2=f(f(m))^2-f(m)=f(f(n))^2-f(n)=n^2$$ Claim 3. $f(f(n))\equiv n\pmod 2$. Proof. We note that $$f(f(n))^2=4f(n)+n^2\equiv n^2\pmod 2$$ Claim 4. $f(0)\in\{0,1,4\}$. Proof. Let $a_0=0$ (and use Claim 1 for the rest of the $a_i$). Then, we get that $a_2=\sqrt{4a_1}$, so $a_1=a^2$ for some $a\in\mathbb Z^+$. Now, this means $a_2=\pm 2a$, so thus $a_3^2=a^4\pm8a$. Now, we note that we can easily bound if $a\geq 4$, then if $a_3^2=a^4+8a$, $$a^4<a_3^2<(a^2+1)^2$$ (as $2a^2+1<8a$ in that range). Similarly, we get if $a_3^2=a^4-8a$, then $$(a^2-1)^2<a_3^2<a^4$$ (as $2a^2+8a>1$). Thus, we see that $a=0,1,2,3$, but $a=3$ gives $3^4\pm3\cdot 8=57,105$, which isn't a perfect square. Thus this gives the current solutions. Claim 5. $f(1)=2$. Proof. Define $a_0=1$ and then we get that as $a_0\equiv a_2\pmod 2$, we have $a_2=\pm(2a+1)$ for some $a\geq 0$. Furthermore, this implies that $$a_1=\frac 14(a_2^2-a_0^2)=a^2+a$$ Note $a\neq 0$ as then we get that $1^2+4f(1)=f(f(1))^2$, so $f(0)=1$, and then we get that $0^2+4f(0)=f(f(0))^2$, so $1=4$, absurd. For the sake of contradiction, let $a>1$. Thus, we get $a_3^2=a^4+2a^3+a^2\pm (8a+4)$. Now, we note the very useful result $(a^2+a)^2=a^4+2a^3+a^2$, $(a^2+a+2)^2=a^4 + 2 a^3 + 5 a^2 + 4 a + 4$, and $(a^2+a-2)^2=a^4 + 2 a^3 - 3 a^2 - 4 a + 4$. Thus, if we use the $+$ from the $\pm$ in $a_3$, then we get that $$(a^2+a)^2<a_3^2<(a^2+a+2)^2$$ Thus, we get $a_3^2=(a^2+a+1)^2$ but as $a_3\equiv a_1$ is even and $a^2+a+1$ is odd, we get a contradiction. Similarly, if we take the $-$ from the $\pm$, we get $$(a^2+a-2)^2<a_3^2<(a^2+a)^2$$ Thus, we get $a_3^2=(a^2+a-1)^2$ but as $a_3\equiv a_1$ is even and $a^2+a-1$ is odd, we get a contradiction. Thus, we have $a=1$, so thus $f(1)=2$. Claim 6. $f(2)=3$. Proof. We note that $$9=1+4f(1)=f(f(1))^2=f(2)^2$$ In particular, we have that $f(2)=\pm 3$. If $f(2)=-3$, then we achieve a contradiction as $$-8=4+4f(2)=f(f(2))^2=f(-3)^2$$ Claim 7. $f(n)=n+1$ on the positive numbers. Proof. We shall induct on $n$. Note that $$f(n)^2 = 4n + f(n-2)^2 = (n+1)^2 \implies f(n) = \pm (n+1)$$ Now suppose $f(n) = -n-1$, then $$4f(n) + f(n-1)^2 = 4(-n-1) + n^2 = n^2 - 4n -4$$ is a perfect square $f(n+1)^2$. However, $n^2-4n+4$ is a perfect square. Thus, we see that $(n-2)^2-f(n+1)^2=8$, which implies $n=5$ (or $-1$, but then $n+1=-(n+1)=0$ so it doesn't matter). However, if $f(5)=-6$, then we have $f(-6)=\pm 1$. $f(-6)\neq 1$ (as otherwise we get $40=(-6)^2+4\cdot 1=f(1)^2=4$ absurd) so $f(-6)=-1$. And then we can derive contradiction as $f(-1)^2=36\pm 4=40.$ Claim 8. $f(n)=1\pm n$ for negative $n$. Proof. We note that first $f(-1)$ has to be nonnegative (as $1+4f(-1)=f(f(-1))^2\geq 0$), so thus $f(-1)=0,1,2$ by the semi-injectivity of $f$. However, we also have that if $f(-1)=1$, then $f(f(-1))\neq 2$, a contradiction. Thus, we get $f(-1)=0,2$. Now, assume $n\leq -2$. We note that $$|f(n)|=\frac 14|f(f(n))^2-n^2|\geq\frac 14|(n\pm 2)^2-n^2|\geq |n|-1$$ as we have $f(n)=0$ if and only if $n=-1,0$ and $f(f(n))\equiv n\pmod 2$. If $f(n)\geq 0$, then we note that the semi-injectivity of $f$ implies $f(n)=0,1,1-n$, but we can check $1$ doesn't work as $$4=f(1)^2=f(f(n))^2=4+n^2\implies n=0$$ and the only roots of $f$ are $-1,0$. Now, we shall assume $f(n)$ is negative, so $f(n)\leq 1+n$. If $f(n)<1+n$, then we get $$|n|-2\leq |f(n)|-1\leq |f(f(n))|=\sqrt{4f(n)+n^2}<\sqrt{n^2+4n+4}=\sqrt{|n|^2-4|n|+4}=|n|-2$$ a contradiction. Thus, $f(n)=1+n$ if it is negative. Claim 9. $f(n)=n+1$ implies $f(n+1)=n+2$ for any $n\in\mathbb Z$. Proof. It suffices to show for $n<0$. We note that $$f(n+1)^2=f(f(n))^2=4f(n)+n^2=(n+2)^2\implies f(n+1)=\pm(n+2)$$ If $f(n+1)=-(n+2)$, then we note that $f(-n-3)=-n-2$. Thus, if $n\leq -4$, we get that $f(-n-3)=f(n+1)$, a contradiction. Now, we take cases for $n\in\{-3,-2,-1\}$. If $n=-3$, then we get that $f(-2)=\pm 1$. If $f(-2)=1$, then we get $$4=f(1)^2=f(f(-2))^2=4f(-2)+4=8$$ absurd. Similarly, if $n=-2$, then $f(-1)=0$. If $n=-1$, then we get $f(0)=\pm 1$. If $f(0)=-1$, then $$0=f(-1)^2=f(f(0))^2=4f(0)+0=-4$$ absurd. This finishes the claim. Now, it's time for the ending. Note that $f(0)=4$ combined with $f(3)=4$ and Claim 2 all come to show $0=\pm 3$. Thus, $f(0)=0,1$, from which we get $$f(x)=x+1$$ $$f(x)=\begin{cases}x+1&x\geq c\\1-x&x<c\end{cases}\qquad c\leq -1$$ $$f(x)=\begin{cases}x+1&x>0\\1-x&x<0\\0&x=0\end{cases}$$ as if $f(0)=0$, then we can never have $f(x)=1+x$ for $x<0$ (otherwise we induct with our last claim to get $f(0)=1$).

We claim that the only $f$ which work are: $f(x)=x+1$, $f(x)=\begin{cases}1-x&\text{ when } x<a\\x+1&\text{ when } x\ge a\end{cases}$, and $f(x)=\begin{cases}1-x&\text{ when } x<0\\0&\text{ when } x=0\\x+1&\text{ when } x>0\end{cases}$. First, consider $f(0)$, which must be $k^2$ for some $k\ge 0$. We need $0\to k^2\to \pm 2k$, so $k^4 \pm 8k$ must be a perfect square. If we take the positive sign, note that the next square of the same parity of $k^4$ is $k^4+4k^2+4\implies 2k\ge k^2+1\implies k\le 1$. Note that $k=0,1$ both yield a perfect square. On the other hand, if we take the negative sign, we need $2k\ge k^2-1\implies k\le 2$. $k^4-8k$ is only a square in this range when $k=0,2$. Hence, function $f$ must satisfy one of the three cases: $0\to 0$, $0\to 1$ or $0\to 4\to -4\to 0$. Similarly, we now investigate $f(1)$. We have that $f(1)=k^2-k$ for some $k\ge 1$. So, this time we need $(k^2-k)^2\pm 8(2k-1)$ to be a square. First considering the $+$ case, we use the exact same bounding as before to get $2k-1\ge k^2-k+1\implies k^2-3k+2\le 0\implies k\le 2$. So, in this case, we only have $k=1,2$ work. On the other hand, the $-$ case gives $2k-1\le k^2-k-1\implies k\le 3$. Here, we get that $k=3$ works. Hence, we have $f$ must satisfy one of the three cases: $1\to 2$, $1\to 0\to 1$, or $1\to 6\to -5$. To eliminate the second case, note that we should have $4f(0)=f(f(0))^2$, but this yields $4=0$, which is a contradiction. On the other hand, if we consider the third case, note $f(f(6))=\pm 4$, but $25+4f(f(6))$ must be a square, so $f(f(6))=-4$. Hence, $1\to 6\to -5\to -4$. We can continue this inductively to get $1\to 6\to -5\to -4\to -3\to -2\to -1\to 0$. Now, from our casework on $0$, we know that either $0\to -1$, $0\to 1$, or $0\to -4$. All three of these cases yield loops in this chain which easily fail. Hence, the third case is impossible as well and we must have $1\to 2$. Now, we claim that when $1\to 2$ occurs, we must have $f(n)=n+1$ for all $n>0$. We can prove this by induction with base cases $n=1,2$. In particular, for the inductive step, we have $f(n)^2=4n+(n-1)^2=(n+1)^2\implies f(n)=\pm(n+1)$. But, if $f(n)=-(n+1)$, then plugging in $n$ into the assertion gives $f(f(n))^2=n^2-4(n+1)=(n-2)^2-8$, which is never a square unless $n=5$. So, the only case where our induction might fail is at $n=5$. In this case, we get $1\to 2\to 3\to 4\to 5\to -6$. The next term is $\pm 1$, but $36\pm 4$ is not a perfect square. Hence, this case is not possible and we have $f(n)=n+1$ for all $n>0$. Note that this eliminates the $0\to 4\to -4\to 0$ case. Now, consider some $k<0$. If $f(k)\ge 1$, then $f(f(k))=f(k)+1$, so $k^2=(f(k)-1)^2$, and $k=1-f(k)$. If $f(k)>0$, suppose there exists some $a$ such that $f(a)=k$. Then, we have that $a^2+4k=(1-k)^2\implies a^2=k^2-6k+1$. However, this is not a square for $k=-1$, and for $k<-1$, note that $k^2-4k+4<k^2-6k+1<k^2-6k+9$. Hence, $a$ never exists. So, if a negative goes to a positive number, it is a leaf on our arrow graph. On the other hand, if $k\to a$ for some $a<0$, we claim that $|a|<|k|$. If we suppose the contrary, then $k^2+4a<(k+2)^2$. We can't have $f(a)$ is positive, since we established earlier that then $k$ would not exist. So, $k+2<f(a)<0$. Hence, $(a+2)^2<a^2+4f(a)<a^2$, which is a contradiction. Hence, we have that $|f(k)|<|k|$ for negative $k$. In fact, by similar bounding, we have that $f(k)<0\implies f(k)=k+1$. If $f(k-1)=k$, then $k$ is now part of a chain and not a leaf, so by earlier logic, $f(k)=k+1$. Now, we consider the smallest value of $k<0$ for which $f(k)=k+1$. If such a value doesn't exist, we either have that such values are unbounded, or don't exist. In the former, note that if $f(x)=x+1$ for any small $x$, we get $x\to x+1\to x+2\to\ldots$, so $x$ is unbounded implies $f(x)=x+1$ for all $x<0$. For the latter, this just means that $f(x)=1-x$ for all $x<0$. On the other hand, if $m$ is the smallest value for which $f(m)=m+1$, note that we get the chain $m\to m+1\to m+2\to\ldots$, so $f(x)=x+1$ for $m\le x<0$. And, if $x<m$, we must have $f(x)=1-x$. To finish, note that in the $0\to 1$ case, we can choose $m$ arbitrarily and get the first and second cases. On the other hand, when $f(0)=0$, if $m$ exists, then $-1\to 0\to 0$, which is a contradiction. Hence, $f(x)=1-x\forall x<0$, leading to the third class of solutions. This exhausts all cases, and hence the three aforementioned classes of solutions are the only ones.

hajimbrak wrote: Find all functions $f : \mathbb{Z} \to\mathbb{ Z}$ such that $$n^2+4f(n)=f(f(n))^2$$ for all $n\in \mathbb{Z}$. Proposed by Sahl Khan, UK What a monstrosity! We claim that all dolutions are of the form $\boxed{f(x) = 1 + x \cdot \frac{x - a}{\mid x - a \mid}}$ for all $x \neq a$ and $\boxed{f(a) = 1 + a}$ for all integers $x$ and for some non-negative integer $a$ and $\boxed{f(x) = 1 + x\cdot \frac{x}{\mid x \mid}}$ for all reals $x \neq 0$ and $\boxed{f(0)= 0}$. Step 1 : Some 'prerequisites' as such. Let $P(n)$ be the assertion of the problem. $P(0) \implies f(f(0))^2 = f^2(0)^2 = 4f(0)$. Now see that $P(f^k(0)) \implies f^{k+2}(0)^2 = f^{k}(0)^2 + 4f^{k+1}(0)$ and we see that$f^2(0) = 2\sqrt{f(0)}$ which means that $f(0)$ is a perfect square. Now, $f^3(0)^2 = f(0)^4 \pm 8f(0)$. If $f^3(0) = f(0)^4 + 8f(0)$, we get that $f(0)^4 \leq f^3(0)^2 = f(0)^4 + 8f(0) \leq (f(0)^2+1)^2$ and if $f^3(0)2 = f(0)^4 - 8f(0)$, then $(f(0)^2-1)^2 \leq f^3(0)^2 = f(0)^4 - 8f(0) \leq f(0)^4$ and simply solving these equations over integers yield that $\boxed{f(0) = 0, 1, 4}$ are the only such values for $f(0)$. Step 2 : The 'most difficult' process. We see that $f(f(1)) \equiv 1 \pmod{2}$ using $P(1)$. We see that similar to the way we solved for $f(0)$, we solve for $f(1)$ and get that $f^2(1) = \pm (2t + 1)$ where $t$ is integer and also observe that $f(1) = t^2 + t$ and we see that $t \neq 0$ or it yields a contradiction, so without loss of generality let $t$ be positive as it doesn't matter much such that $t \neq 1$ for now. $therefore f^3(1)^2 = t^4 + t^3 + t^2 \pm (8t+4)$ and so if we have $f^3(1)$ value with $+(8t+4)$, we'll yield that $f^3(1)^2$ lies between $(t^2+t)^2$ and $(t^2+t+2)^2$ easily which means that $f^3(1)^2 = (t^2+t+1)^2 \equiv f(1)^2 \pmod{2}$, a contradiction since $f(1)$ is even. So, $t = 1$ and hence using few verification, we find that $f(1) = 2$. I'll skip the proof for $f(2) = 3$ as my PC is overheating and will add later, but it is really similar to the way we solved $f(0), f(1)$. Step 3 : Induction FTW Using induction on $n+1$ , we see that $f(n+1) = \pm (n +2)$ using $P(n)$ and so, if $f(n+1) = - n - 2$ we would have that using $P(n)$ that $f(n+1)^2 - (n+2)^2 = -8$ which is a easily handle-able case which yields contradiction nevertheless. Now, $f(n) = n+1$ for all positive reals. (which shows that $f(0) \neq 4$. Using $P(-1)$ we conclude that $f(-1) \in \{ 0, 2 \}$ by using basic simplifications. If $f \leq -2$, then $P(2) \implies \mid f(n) \mid \geq \mid n \mid + 1$. But using the fact that $f(u) = f(v)$ if and only if $u = \pm v$ yields that $\mid f(n) \mid \geq 1$. But we see that if $f(n) = n + 1$ for some $n$ implies $f(k) = k + 1$ for all $k \geq n$, because if $f(k) = -(k+1)$ for some $k > n$, we get $f(-k -3) = f(k - 1) = -k- 2$ which then boils down to three cases - $n = 0, 1, 2, 3$ all of which can be handled swiftly. So, we have our desired results using all above results, which, I in the first line wrote it in the lazy form or in other words the form which I haven't derived in the same way but writing it like that saves my time. Also sorry for a rushed proof and I'll redesign it later (I might forget my arguments so posted the dolution immediately)

Here are some steps for a more NT flavored solution. Step 1: Note that any solution $(x,y,z)$ to $x^2+4y=z^2$ is of the form $(a-b,ab,a+b)$. so $$f(n) = b_n(n+b_n) \ \ \ \ \ \text{and} \ \ \ \ \ f(f(n))=n+2b_n$$ For some sequence $b_n$ of integers. Step 2: The pair $(x,y)=(b_n,b_{f(n)})$ solves the equation: $$y^2 + yx(n+x) - [x+(n+x)] = 0$$ This follows immediately from step 1 applied to the integers $n$ and $f(n)$. Step 3: The previous quadratic equation can be solved (think about the discriminant) to deduce that for all $n\in \mathbb{Z}$, $b_n$ has to be one of the following possibilities: $$1, 1-n, -\frac{n}{2}, -n , 0$$ Step 4: Deduce that $f(n)$ is $1+n$ or $1-n$, unless $n=0$, it's possible to have $f(0)=0$. Step 5: Now it's easy to describe all solutions.

In a way, it's a kind of meditation. Apply the condition to $0, f(0)$ to yield a classical square difference bound on $f(f(0))$, giving three cases after continuous application of the condition on $f^k(0)$: Case A: $f(0) = 0$ Case B: $f(0) = 1, f(n) = n+1$ for all $n \geq 0$ Case C: $f(0) = 4, f(4) = -4, f(-4) = 0$ Call a number such that $f(n) = n+1$ a flower and a number such that $f(n) = -n+1$ a tomato. Notice that if $f(n)$ is a flower then $f(n)$ is either a flower or a tomato by equation solving. Notice that if $f(n)$ is a tomato, then $f(n) = 0$ or $f(n) = 6$ by square bounding and euclidean algorithm. Now consider Case B. Notice that for a negative number $n$, if $f(n)$ is negative then $f(f(n))$ is positive or $f(f(n)) > n$, and $f$ is strictly increasing on nonnegative numbers, hence $f(f(n)) > n$ for all $n$. Thus we induct down starting from $-1$. $f(f(-1))$ is a flower and $f(-1)$ is not a tomato so $f(-1)$ is a flower so $f(-1)$ is either a flower or tomato. The condition is that all numbers above a number are either a flower or a tomato. Clearly the identical argument holds as we induct down, and $f(i)$ must be a tomato if $f(i+1)$ is a tomato, so we get the following valid solution sets: $f(x) = \begin{cases} x+1 & x \geq c \\ -x + 1 & x < c \end{cases}$ for some $c \leq 0$ if there exists a tomato, and $f(x) = x+1$ if all integers are flowers. Call these solutions tranquil. We now look for nontranquil solutions. Again, we apply classical square difference bounding to the value of $f(f(-1))$ by applying the condition to $-1, f(-1)$, then get the following cases after continuous application of the condition on $f^k(-1)$: Case X: $f(-1) = 0, f(0) = 1$, all nonnegative integers are flowers. Case Y: $f(-1) = 2, f(2) = 3$, all integers at least two are flowers. Case Z: $f(-1) = 6, f(6) = -5, f(-5) = -4, f(-4) = -3, f(-3) = -2, f(-2) = -1, f(-1) = 0$. Notice that Case X implies tranquility as it implies Case B. Furthermore notice Case Z is not compatible with neither Case A, B, or C, since in Case A the condition fails for $-1$, in Case B $-1$ is neither a flower or a tomato, and in Case C $f(-4) = 0$. Finally, consider case Y. Notice $f(1) = 0$ violates the condition for $1$, so $f(f(1)) > 1$ for the same reason as in Case B and $1$ cannot be a tomato, so $1$ is a flower. Furthermore, no element maps to $0$ since it would violate the condition on that element, so the same argument as in Case B applies, giving us that $f(1) = 2, f(-1) = 2$, and by inducting down, all negative numbers are tomatoes. This nets the final valid and nontranquil solution: $f(x) = \begin{cases} x+1 & x > 0 \\ 0 & x = 0 \\ -x + 1 & x < 0 \end{cases}$ And we are done. $\blacksquare$

Let $f(f(n))^2=n^2+4f(n)$ be eq.$(*)$. First, $f(f(1))$ is odd. For $k\geqslant 0$, let $f(f(1))=\pm 2k \pm 1$. Whence $f(1)=k^2+k$. If $k=0$, then $f(0)=1$ (since by $(*)$ $f(0)\geqslant 0$), and contradiction by $(*)$. If $k>1$, then $(*)$ for $f(1)$ implies $f(f(f(1)))^2 \in \{ (k^2+k+1)^2, (k^2+k-1)^2\}$. This is absurd, since $k^2+k$ has same parity as $f(f(f(1)))$. So $k=1$ and $f(1)=2$, so $f(2)=\pm 3$ and $(*)$ gives $f(2)=3$. By induction, $f(n)=\pm (n+1)$ for all $n>0$. If $f(a)=-a-1$ for some $a>1$, then $(*)$ gives $a=5$, so $f(5)=-6$ and $f(-6)=\pm 1$. Again contradiction from $(*)$ for $-6$. Thus, $f(n)=n+1$ for all $n>0$. Since $f(0)\geqslant 0$, we have $f(0)=0$ or $f(f(0))=f(0)+1$. The latter in $(*)$ implies $f(0)=1$. If $f(0)=0$, then $f$ is injective at $0$. Also $f(-1)\geqslant 0$, and similarly $f(-1)\in \{0,2\}$. Let $x<-1$. If $f(x)>0$, then $f(f(x))=f(x)+1$ and so $f(x)=1-x$. Clearly $f(x)=0$ yields a contradiction. If $f(x)<0$, then $(*)$ implies $f(x)\leqslant x+1$, which easily gives $f(x)=x+1$. So for any $x<0$, $f(x)=\pm x+1$. If for some $m<-1$, $f(m)=m+1$, then inducting we get $f(n)=n+1$ for all $n\geqslant m$ and $f(n)=1-n$ else. So the solution is: $f(n)\equiv n+1$ or for some $m<0$, $$f(n)=\begin{cases} 1+n & \text{for } n\geqslant m \\ 1-n &\text{for } n<m\end{cases}$$ or maybe, $$f(n)=\begin{cases} 1+n &\text{for } n>0 \\ 1-n &\text{for } n<0 \\ 0 &\text{else} \end{cases}$$ All of these work.

Define a chain as a sequence of distinct integers $a_1, a_2, \dots$ such that $$a_i^2 + 4a_{i+1} = a_{i+2}^2$$ and $a_{i+1}$ is completely determined by $a_i$. The functional digraph of $f$ is then composed of such chains. Claim: $f(f(n)) \equiv n \pmod{2}$. Likewise, $a_i \equiv a_{i+2} \pmod{2}$ in a chain. Proof. Immediate. $\blacksquare$ Claim: $f(n) = n + 1$ for $n \ge 1$. Proof. We claim that only the chain beginning at $1$ is $1, f(1) = 2, f(f(1)) = 3, \dots$. Suppose that $1, f(1), f(f(1)), \dots$ is a chain. Then $f(f(1))$ must be a odd integer, and $f(1) = \frac{1}{4}(f(f(1))^2 - 1)$. Furthermore, one of $f(1)^2 \pm 4f(f(1))$ must be a perfect square. This can only hold if $f(f(1)) \ge f(1) - 1$ due to the difference of consecutive squares. $$f(f(1)) \ge \frac{1}{4}(f(f(1))^2 - 1) - 1$$ only holds for $|f(f(1))| \le 5$. The only possible chains start out as then $1, 0, \pm 1, \dots$, $1, 2, \pm 3, \dots$, $1, 6, \pm 5, \dots$. It turns out that choosing the sign of each number while building the chain is forced, so we end up with the following result. The first case becomes $1, 0, 1, 2$, and thus can't be a chain. The second case becomes $1, 2, 3, \dots$ as desired. The final case becomes $1, 6, -5, -4, -3, -2, -1, 0, 1, 2$, and thus can't be a chain. $\blacksquare$ Claim: $f(0) \in \{0, 1\}$. Proof. Consider the possible chains starting with $a_1 = 0$ in the digraph. $f(0)$ must then be equal to $\frac{1}{4} \cdot f(f(0))^2$ and is thus a perfect square. First assume $f(f(0)) = 0$. This implies $a_2 = 0$, giving the chain $0, 0, 0, \dots$. Next, assume $f(f(0)) \ne 0$. This implies in turn that $f(0) > 0$, so it must hold that $f(0) + 1 = f(f(0))$, or that $$\frac{1}{4} \cdot f(f(0))^2 + 1 = f(f(0))$$ which only holds if $f(f(0)) = 2$, giving the only other chain of $0, 1, 2 \dots$. $\blacksquare$ Claim: $f(-1) \in \{0, 2\}$ Proof. First consider the chain $-1, f(-1), f(f(-1)) \dots$. $f(-1) \ge 0$ must follow since $-1 + 4f(-1) = f(f(-1))^2$. Since $f(-1) + 1 = f(f(-1))$, it must follow that $f(-1) \in \{0, 2\}$. $\blacksquare$ Claim: For $x < 0$, $f(x) = 1 \pm x$. Proof. Consider potential chains $x, f(x), f(f(x)), \dots$ such $x \le -2$. If $f(x) > 0$, then $f(f(x)) = f(x) + 1$, so $$x^2 + 4f(x) = (f(x) + 1)^2$$ implies that $1 - x = f(x)$. Note that this claim is independent of the induction. If $f(x) = 0$, this implies that $x = -1$. Else, assume $f(x) < 0$. If $f(f(x)) \ge 0$ holds as well, this implies that $f(f(x)) = 1 - f(x)$ which means that $$x^2 = f(x)^2 - 6f(x) + 1$$ which is a contradiction by difference of squares. Thus, $f(f(x)) < 0$ holds as well. By repeating this, it follows that the chain $$x, f(x), f(f(x)), \dots$$ is negative until $-1$ and then $0$ occurs. It must also terminate similarily. We can then induct backwards to get that the chain is an AP with common difference $1$. $\blacksquare$ Claim: If $f(n) = n + 1$, then $f(n + 1) = n + 2$. Proof. Follows since $f(n + 1) = f(f(n))$ and then the assertion. $\blacksquare$ Thus, we can now fully classify $f$. First assume that $f(0) = 1$. Let $c \le 0$ be minimal such $f(c) = c + 1$. If no such $c$ exists, then $f(x) = x + 1$ works. Else, $$f(x) = \begin{cases} 1 + x & x \ge c \\ 1 - x & x < c \end{cases}$$ which can be seen to work. Else, suppose $f(0) = 0$. This implies that $f(-1) = 2$, which forces $$f(x) = \begin{cases} 1 + x & x > 0 \\ 0 & x = 0 \\ 1 - x & x \le 0 \end{cases}$$ and also works.