The nice fact about this problem is that $f(n)=n^2$ is not the only solution.(This fact is not found by me)

I found $f(n)=n^2+4kn+2k^2$ is other solution,is there any other solution?

This generalizes Iran TST 2011 problem 12.

Answer $f_k(x)=x^2+4kx+2k^2$ for any $k \in \mathbb N_0$. Solution Direct check shows that $f_k$ is indeed a solution for any $k \in \mathbb N_0$: $f_k(x)+2xy+f_k(y)=x^2+4kx+2k^2+2xy+y^2+4ky+2k^2=(x+y+2k)^2$. To prove that any solution $f$ has the said form, introduce a function $g \colon \mathbb N \times \mathbb N \to \mathbb N$ such that $f(x)+2xy+f(y)=g^2(x,y)$ for any $x,y \in \mathbb N$.

variables from $\mathbb N$ ) 0. $f(x)+2xy+f(y)=g^2(x,y)$ 1. $f(x)<f(x+1)$ 2. $g(x,y)<g(x+1,y),\;g(x,y)<g(x,y+1)$ 3. $x+y \le g(x,y)$ 4. $(f(x+1)-f(x))-(2x+1)=2h(x), \text{where } h \colon \mathbb N \to \mathbb N_0$ 5. $\exists u \in \mathbb N, d=h(u) \in \mathbb N_0 \; \forall x \colon d \le h(x)$ 6. $\exists a \in \mathbb Z \; \forall x \colon x^2+2dx+a \le f(x)$ 7. $g(x,y) \le x+y+h(y)$ 8. $\exists b \in \mathbb Z \; \forall x \colon f(x) \le x^2+2dx+b$ 9. $(x+y+d)^2+(2a-d^2) \le g^2(x,y) \le (x+y+d)^2+(2b-d^2)$ 10. $\exists T \in \mathbb N \; \forall x,y \colon x+y > T \implies g(x,y)=x+y+d$ 11. $x>\tfrac T 2 \implies f(x)=x^2+2dx+\tfrac {d^2} 2$ 12. $f(x)=x^2+2dx+\tfrac {d^2} 2$ 13. $\exists k \in \mathbb N_0 \; \forall x \colon f(x)=x^2+4kx+2k^2$

0.> The equation implied by the condition. 1.> Assume the opposite, there exists some $x$ such that $t=f(x)-f(x+1)\ge 0$. If $t$ is even, let $y=\frac t 2 + 1$, otherwise let $y=\frac {t+1} 2$. Anyway, $y \in \mathbb N$. 0$[x \gets x+1]$ : $f(x+1)+2(x+1)y+f(y)=g^2(x+1,y)$, 0: $f(x)+2xy+f(y)=g^2(x,y)$. Subtracting, we get: $-t+2y=g^2(x+1,y)-g^2(x,y)$. Note that $2y-t \in \{1,2\}$ but the least possible positive difference between squares of two natural numbers is $2^2-1^2=3$, a contradiction. 2.> By comparing 0 with 0$[x \gets x+1]$ using 1 and by comparing 0 with 0$[y \gets y+1]$ using 1$[x \gets y]$, it's easy to get the result. 3.> Induction on $z=x+y$. 0$[x \gets 1, y \gets 1]$ : $4 \le f(1)+2+f(1)=g^2(1,1) \implies 2 \le g(1,1)$ gives the base case $z=2$. 2 gives the induction step because each pair $(x,y)$ with $x+y=z+1$ can be obtained from at least one pair $(x,y)$ with $x+y=z$ by increasing one of components, 2 shows that $g(x,y)$ then also increases at least by $1$. 4.> Due to 2$[y \gets x]$ and 2$[x \gets x+1, y \gets x]$, $g(x,x)<g(x+1,x)<g(x+1,x+1)$. 0$[x \gets x+1, y \gets x+1]$ : $2f(x+1)+2(x+1)^2=g^2(x+1,x+1)$, 0$[y \gets x]$ : $2f(x)+2x^2=g^2(x,x)$. Note that both $g^2(x+1,x+1)$ and $g^2(x,x)$, being even, are divisible by $4$. Subtracting, we get: $2(f(x+1)-f(x)+2x+1)=g^2(x+1,x+1)-g^2(x,x)$. The right part, being the positive difference between two even perfect squares, is not less than $(g(x,x)+2)^2-g^2(x,x)=4g(x,x)+4 \ge 8x+4$, due to 3$[y \gets x]$, and is also divisible by $4$. Thus the number $f(x+1)-f(x)+2x+1$ is even and is not less than $4x+2$. 5.> This is just a definition of a minimum point of the function $h \colon \mathbb N \to \mathbb N_0$. 6.> 5$[x \gets t]$, 4$[x \gets t]$ : $2d \le 2h(t)=(f(t+1)-f(t))-(2t+1)$. Summing this up for all $t$ from $1$ to $x-1$, we get: $2d(x-1) \le (f(x)-f(1))-(x^2-1)$, so $x^2+2dx+(f(1)-2d-1) \le f(x)$ and we can take $a=f(1)-2d-1$. 7.> Subtracting 0: $f(x)+2xy+f(y)=g^2(x,y)$ from 0$[y \gets y+1]$ : $f(x)+2x(y+1)+f(y+1)=g^2(x,y+1)$, we get: $(f(y+1)-f(y))+2x=g^2(x,y+1)-g^2(x,y)$. The left part is $2h(y)+(2y+1)+2x$, due to 4$[x \gets y]$. The right part is a positive (due to 2) difference of two perfect squares, it is not less than $(g(x,y)+1)^2-g^2(x,y)=2g(x,y)+1$. Thus, $2g(x,y)+1 \le 2h(y)+(2y+1)+2x$. 8.> Squaring 7$[y \gets u]$ and taking into account 0$[y \gets u]$ and 5, we get: $f(x)+2xu+f(u)=g^2(x,u) \le (x+u+d)^2$, that is $f(x)+2xu+f(u)\le x^2+2xu+2xd+(u+d)^2$, from which $f(x) \le x^2+2xd+((u+d)^2-f(u))$ and we can take $b=(u+d)^2-f(u)$. 9.> Summing 6 with 6$[x \gets y]$ and adding $2xy$ to both parts, we get the left part due to 0. Similarly, summing 8 with 8$[x \gets y]$ and adding $2xy$ to both parts, we get the right part. 10.> Take any $x,y$ and let $s=x+y+d$. Note that if $(s-1)^2<s^2+(2a-d^2)\le g^2(x,y) \le s^2+(2b-d^2)<(s+1)^2$, then $g(x,y)=s$. However, this is always the case when $s$ (we may say $x+y$) is large enough for $-2s+1<2a-d^2$ and $2b-d^2<2s+1$ to be true. 11.> Let $x>\tfrac T 2$. 10$[y \gets x]$ : $g(x,x)=2x+d$. 0$[y \gets x]$ : $2f(x)+2x^2=g^2(x,x)=(2x+d)^2$. Thus, $f(x) = \tfrac {4x^2+4dx+d^2-2x^2}2=x^2+2dx+\tfrac {d^2}2$. 12.> Take any $y>T$. Then $x+y>T$. 0, 10: $f(x)+2xy+f(y)=g^2(x,y)=(x+y+d)^2$. Due to 11$[x \gets y]$ : $f(y)=y^2+2dy+\tfrac {d^2}2$, $f(x)=(x+y+d)^2-2xy-\left(y^2+2dy+\tfrac {d^2}2\right)=x^2+2dx+\tfrac {d^2}2$. 13.> $d \in \mathbb N_0$, due to 5. However, $d$ cannot be odd because then, plugging any $x$ in 12, we would not get an integer at the right part. Hence, $d=2k$ for $k \in \mathbb N_0$. Plugging this back into 12, we get the desired equality.

infact, the problem can solve in $f:\mathbb{N} \to \mathbb{Z}$, my solution : first we get $2f(n)+2n^2$ are square for all n (1) -> $f(0)=2k^2$ prove by induction : assum $f(c)=c^2+4kc+2k^2$ for every $c \le n$ we will prove $f(n+1)$ is also $(n+1)^2+4(n+1)k+2k^2$ for all $m$ large enough we get $f(n+1)+2(n+1)m+f(m)=f(n+1)-f(n)+2m+f(n)+2mn+f(m)$ are perfect square note that the difference between $2$ square never divisible by $2$ but not divisible by $4$ and $f(n)+2mn+f(m)$ are square $-> f(n+1)-f(n)$ must be odd (if it not there exits m such that $f(n+1)-f(n)+2m \equiv 2(\mod 4))$ choose $f(n+1)-f(n)+2m=p$ where $p$ are a prime let $f(n)+2mn+f(m)=c^2$ and $f(n+1)+2(n+1)m+f(m)=d^2 $ $-> d^2-c^2=p>0 -> (d-c)(d+c)=p -> c=\frac{p-1}2-> f(m)=\frac{(p-1)^2-4f(n)-8mn}4$ and $m=\frac{p+f(n)-f(n+1)}2$ using $(1)$ we get $2f(m)+2m^2=p^2-p(2n+1+f(n+1)-f(n))+2n(f(n+1)-f(n))-2f(n)+\frac{(f(n+1)-f(n))^2+1}2=p^2-2pA+B$ are perfect square $(2)$ note that $(2)$ hold for all prime $p$ let $p$ are large enough we must have $B=A^2$ (exits integer $A,B$ cause $f(n+1)-f(n)$ odd) $-> (f(n+1)-f(n)+2n-1)^2=4(2f(n)+2n^2)$ since $f(n)=n^2+4kn+2k^2 -> 2f(n)+2n^2=(2n+2k)^2$ are perfect square so there will be $2$ case case 1: $f(n+1)-f(n)+2n-1=4n+4k-> f(n+1)= n^2+2n+1+4k(n+1)+2k^2=(n+1)^2+4k(n+1)+2k^2$ case 2: $f(n+1)-f(n)+2n-1=-4n-4k-> f(n+1)=n^2-6n+1-4k+4kn+2k^2$ if $n>1 f(n+1)+f(n-2)+2(n+1)(n-2)=4n^2-12n+1+4k(2n-3)+4k^2=(2n-3+2k)^2-8$ are a perfect square $->n+k=3-> n=2,k=1-> f(3)=-2$ but $2f(3)+18=14$ not a square if $n=1 f(2)=2k^2-4, but f(2)+f(0)=4k^2-4$ are perfect square$-> k=1 or f(2)=2$ but $f(2)+2+f(1)=7$ not a square -> this case only happend when $n=0$ meaning $f(1)=2k^2-4k+1= 2(-k)^2+4(-k)+1$, proving similar $f(n)=n^2-4kn+2k^2$ retry, $f(m)+f(n)+2mn=m^2+2mn+n^2+4km+4kn+4k^2=(m+n+2k)^2$ allway are a perfect square so the solution are $f(n)=n^2-4kn+2k^2$ where $k$ is a constant integer.

Let $f(m)+2mn+f(n)=x^2$ and $f(m)+2m(n+1)+f(n+1)=y^2$. Then $2m+(f(n+1)-f(n)) = y^2 - x^2$. Let $f(n+1)-f(n) = k.$ By considering$\pmod{4}$, it is clear that $k$ is odd, so we can choose $m$ such that $2m = p-k$. Now $y^2 - x^2 = (y-x)(y+x) = p$, so $y = \frac{p+1}{2}, x = \frac{p-1}{2}$. Next consider $f(m)+2m(n+2)+f(n+2) = z^2$. Then $z^2 - \frac{p+1}{2}^2 = 2m + (f(n+2)-f(n+1)) = p+c$, where $c = f(n+2)-2f(n+1)+f(n)$. It is clear that $\frac{p+1}{2}^2 < \frac{p+1}{2}^2 + (p+c) < \frac{p+5}{2}^2$ for sufficiently big $p$; hence $\frac{p+1}{2}^2 + (p+c) = \frac{p+3}{2}^2$ for all large $p$. But this implies that $c = f(n+2)-2f(n+1)+f(n) = 2$, so $f(n) = n^2 + an + b$ for some constants $a,b$. The final step is a technical exercise. We substitute the function with $m=1$ into the original equation to obtain $n^2+(2a+2)n+(a+2b+1)$ is a perfect square $\implies$ $4n^2+(4a+4)n+(2a+4b+1) = (2n+(a+1))^2 + (4b-a^2)$ is a perfect square $\implies$ $4b-a^2 = 0$ by considering sufficiently large $n$. Hence $f(n) = n^2 + 4kn + 2k^2$ for all $n$; checking, all such functions work.

Solution with (i.e. mostly by) ewan. Denote the assertion as $P(m,n)$. For notation, define $g(m,n)=\sqrt{f(n)+2mn+f(m)}$. Claim 1: $f(x)$ is strictly increasing. Proof: Suppose $f(x)\ge f(x+1)$. Then, consider $P(x,m)$ and $P(x+1,m)$. As we increase $m$ by 1, $g(x+1,m)^2-g(x,m)^2$ increases by 2, and we can continue incrementing $m$ until $g(x+1,m)^2-g(x,m)^2\in\{1,2\}$. As neither is possible for the difference of positive squares, we must have that $f(x)<f(x+1)$, as desired. Claim 2: $f(x)\equiv x\pmod 2$. Proof: We have $g(x,x)^2=2f(x)+2x^2=2(f(x)+x^2)$. If $f(x)+x^2\equiv 1\pmod 2$, then we have $g(x,x)^2\equiv 2\pmod 4$, which is impossible. So, $f(x)\equiv -x^2\implies f(x)\equiv x\pmod 2$. In particular, this implies that $f(1)-f(2)$ is odd. Claim 3: We can find arbitrarily large $x$ such that $f(x)>(x-C)^2$ for some constant $C$. Proof: Consider $P(1,m)$ and $P(2,m)$. At $m=1$, $g(2,m)^2-g(1,m)^2\equiv 1\pmod 2$. Once again, we can increment $m$ to increase this difference by any even number. So, we can force $g(2,m)^2-g(1,m)^2$ to be a large prime $p$, for some $m\gg 1$. Then, we must have that $$g(2,m)+g(1,m)=p\ge 2m\implies \sqrt{f(m)+4m+f(2)}+\sqrt{f(m)+2m+f(1)}\ge 2m$$which implies $f(m)+4m+f(2)\ge m^2$, or $f(m)>(m-C)^2$, as desired. Claim 4: $f(x)=(x+a)^2+C$, for some integers $a,C$. Proof: For a given $x$, consider a very large $N\gg x$ such that $f(N)>(N-c)^2$. Then, $P(N,x)$, $P(N,x+1)$, and $P(N,x+2)$ give that $$f(N)+2xN+f(x),f(N)+(2x+2)N+f(x+1),f(N)+(2x+4)N+f(x+2)$$are all squares. As $N$ is very large, each one is around $2N$ larger than the previous one. Furthermore, all squares are at least on the order $N^2$. So, they must be consecutive. This gives that $f(x),f(x+1),f(x+2)$ are equal to $k^2+C,(k+1)^2+C,(k+2)^2+C$ for some $C$. Now, note that $f(x+1)-f(x)$ uniquely determines $k$ and $C$, so we must have the same $C$ for any $x$, yielding the desired form. Of course, this means that $f(x)$ must be a monic quadratic expression with even linear coefficient. Claim 5: $f(x)=x^2+4kx+2k^2$. Now, we just plug back into our original assertion. Letting $f(x)=x^2+2ax+b$, we get that $m^2+2mn+n^2+2a(m+n)+2b$. If we let $m,n\gg 1$, bounding implies that this must be $(m+n+a)^2$, so $b=a^2/2$. This means $a$ is even, so set $a=2k$, and substituting back in gives our desired answer. So, we have $f(x)=x^2+4kx+2k^2$ for any nonnegative $k$.

What a silly problem. The answer is $f(n)=n^2+4kn+2k^2$ for some nonnegative integer $k$. Claim. For all $m$, $f(m+2)=2f(m+1)-f(m)+2$. Proof. Take an arbitrary integer $n$. By the problem statement there are integers $a$, $b$, $c$ with \begin{align*} a^2&=f(m)+2mn+f(n),\\ b^2&=f(m+1)+2mn+2n+f(n),\\ c^2&=f(m+2)+2mn+4n+f(n). \end{align*}Then I claim that we can select $n$ such that $c>b$, $p=f(m+1)-f(m)+2n$ is prime, and $2n>f(m+2)-3f(m+1)+2f(m)-6$. For the first condition, we will show $f(m+2)>f(m+1)$ always. Assume for contradiction otherwise, and consider $c^2-b^2=f(m+2)-f(m+1)+2n$. If $f(m+2)-f(m+1)\le0$, we can choose $n$ such that $c^2-b^2\in\{1,2\}$, both of which are absurd. For the second condition, $f(m+1)-f(m)+2n$ is the difference between two squares, no matter the choice of $n$, but if this quantity is always even, then it is at some point $2\pmod4$, which is impossible. Finally the third condition is possible since we can take $n$ sufficiently large. Subtracting the definitions of $a^2$ and $b^2$, we have $p=b^2-a^2$, whence $a=\tfrac12(p-1)$ and $b=\tfrac12(p+1)$. Now I claim that $c=\tfrac12(p+3)$. Assume for contradiction otherwise. Since $c>b$, we must have $c\ge\tfrac12(p+5)$. This rearranges to \begin{align*} \left(\frac{p+5}2\right)^2&=f(m+2)-f(m+1)+2n+\left(\frac{p+1}2\right)^2\\ \implies2(p+3)&\le f(m+2)-f(m+1)+2n\\ \implies 2n&\le f(m+2)-3f(m+1)+2f(m)-6, \end{align*}which violates the third condition. Now \begin{align*} f(m+2)-f(m+1)&=\left(\frac{p+3}2\right)^2-\left(\frac{p+1}2\right)^2-2n\\ &=f(m+1)-f(m)+2, \end{align*}as desired. $\blacksquare$ Hence $f$ is a monic quadratic, so let $f(n)=n^2+un+v$. Assuming $m=n$ in the problem statement, we have $4n^2+2un+2v$ is always a perfect square. With $n$ sufficiently large, we must have \[4n^2+2un+2v=\left(2n+\frac u4\right)^2,\]It follows that $u=4k$ and $v=2k^2$ for some $k$, so we are done.

Really nice problem ! My solution is a bit long, but the ideas involved are fairly simple . We claim that the only solutions are $$\boxed {f(n)= (n+2\ell)^2 -2\ell^2}$$for some integer $\ell \geq 0$. It is easy to see that it works . Call the assertion as $P(a,b)$ . Write : $$P(a,n+1) \implies f(a)+2an+ 2a+f(n+1) =x^2$$$$P(a,n) \implies f(a)+2an+f(n) =y^2$$ Hence we have that $$(f(n+1)-f(n)) +2a =x^2-y^2$$For $\pmod 4$ reasons , this means that $f(n+1)-f(n)$ is always odd . Write $f(2)-f(1)=2k+1$ and choose $a$ such that $2a+2k+1=p$, where $p$ is a odd prime . Next if , $$ f(a)+4a+f(2)^2=u^2 , f(a)+2a+f(1)^2=v^2$$then we must have that $u = \frac {p+1}{2}$ and $v=\frac {p-1}{2}$ Hence we can write : $$ P(a,2) \implies f(a)+4a+f(2)^2= \left(\frac{p+1}{2}\right)^2 = (a+k+1)^2 $$$$ \implies f(a) = (a + \underbrace {(k-1)}_{=b}) + \underbrace {(k+1)^2-(k-1)^2-f(2)}_{=c}$$$$ \implies f(a)=(a+b)^2+c$$Where $b$ and $c$ are as defined above. Hence there are infinitely many $a$ that satisfy the above relation . Pick such a $a$ . Note that $$P(a,a) \implies 2( (a+b)^2+c)+2a^2 = x^2 \implies (2a+b)^2 +(b^2+2c)=r^2$$ We claim that $b^2+2c=0$ . Take a very large $a$ such that $2a > \mid b^2+2c \mid$ . Hence we can "squeeze" $r^2$ as defined above between two consecutive squares as follows : $$(2a+b-1)^2 < r^2 \leq (2a+b)^2$$$$(2a+b)^2 \leq r^2 < (2a+b+1)^2$$ Hence , $$(2a+b)^2=(2a+b)^2+(b^2+c) \implies b^2+c=0$$. Hence , $\exists \ell \in \mathbb Z$ , such that $b=2\ell$ and $c= -2\ell ^2$ Hence for infinitely many $n \in \mathbb N $ , we have : $$ f(n)= (n+2\ell)^2-2\ell^2$$ Next we pick a arbitrary $n$ and a $a$ that satisfies the above relation . Note that $$P(a,n) \implies z^2=f(a)+2an+f(n)=(a+2\ell)^2-2\ell^2 +2an +f(n) = (a+n+2\ell)^2 + \underbrace {(f(n)-n^2-4n\ell-2\ell^2)}_{=s}$$ Using the same trick , choose $a$ huge with $2a >\mid s \mid $ Hence we have $$(a+n+2\ell)^2 \leq (a+n+2\ell)^2+s < (a+n+2\ell+1)^2$$and $$(a+n+2\ell-1)^2 < (a+n+2\ell)^2+s \leq (a+n+2\ell)^2$$ Hence $$ (a+n+2\ell)^2+s = (a+n+2\ell)^2=0 \implies s=0$$$$ \implies f(n)= (n+2\ell)^2 -2\ell^2 .$$ Next note that if $\ell <0$ then $f(-2\ell) \in \mathbb N$ , so $-2\ell^2 \in \mathbb N$ ($\rightarrow \leftarrow$) . Hence $\ell \geq 0$ and $\forall n \in \mathbb N$ , we have: $$f(n)=(n+2\ell)^2-2\ell^2$$We are done. $\blacksquare$

$-> (f(n+1)-f(n)+2n-1)^2=4(2f(n)+2n^2)$ Can you explain me this pls

nice problem here is a different aproach , with the same idea as any problem of this type. . let $f(m)+2mn+f(n)=p(m,n)^2$ and $f(m)+m^2=2T(m)^2$ . now we clearly have $2|f(m)-m$ so $f(2)$ is even and $f(1)$ is odd. . now we write $Q(n)=p(n,2)^2-p(n,1)^2=2n+f(2)-f(1)$ now define $A=\{n | 2n+f(2)-f(1) \in P \}$ where $P$ denotes the set of prime numbers . now let $n \in A$ checking $Q(n)$ gives $p(n,2)=p(n,1)+1$ and also $p(n,2)=n +\frac{f(2)-f(1)+1}{2}$ which gives $f(n)+4n+f(2)=(n+\frac{f(2)-f(1)+1}{2})^2$ so we can write $f(n)=n^2 +an +b$ for $n \in A$ and fixed $a,b$ . now let $m,n \in A$ we get $(n+m)^2+a(n+m)+2b=p(n,m)^2$ clealy we must have $a=4k , b=2k^2$ so $f(n)=n^2+4kn +2k^2$ for infinitly many $n$ . now we finish the proof this way let $n \in A$ so $f(m)+2mn+n^2+4kn+2k^2=p(m,n)^2$ lets write $f(m)=m^2+4km+2k^2+g(m)$ so $g(m)+(m+n+2k)^2=p(m,n)^2$ . so $g(m)$ is the difference of infinitly many squares so $g(m)=0$ giving $f(n)=n^2+4kn+2k^2$ which the funny thing is all of these work! and we are done

Nice problem! Answer: $f(n) =n^2+4kn+2k^2$ Let $g(m,n)^2 = f(n) + 2mn + f(m)$, then $g(m,2)^2 - g(m,1)^2 = 2m + f(2) - f(1) = 2m + C$ with $C = f(2) - f(1)$. If $C$ is even then we can select $m$ such that $2m + C \equiv 2 \pmod 4$ then no exists a solution for $x^2 - y^2 = 2m+C \equiv 2 \pmod 4$ So we have $C$ is odd then we can select $m$ such that $2m + C = p$ is prime. Then: $$g(m,2)^2 - g(m,1)^2 = p \implies (g(m,2) - g(m,1))(g(m,2)+g(m,1))=p$$ Then $g(m,2) - g(m,1)=1$ and $g(m,2)+g(m,1)=p \implies g(m,1)= \frac{p-1}{2} = m + \frac{C-1}{2}$. Then: $( m + \frac{C-1}{2})^2 = f(1) + 2m + f(m)$ Then exists $A, B$ integers such that $f(m) = m^2 + 2Am + B$ for infinites $m$, we call this integers GOOD. Let $n_0$ an arbitrary positive integer and $m$ a GOOD number. Then: $$g(m,n_0)^2 = f(n_0) +2mn_0 + m^2 + 2Am +B = (m + (A+n_0))^2 + B + f(n_0) - (A+n_0)^2 $$ We can choose a very large $m$ so $B+f(n_0) = (A + n_0)^2$ for any $n_0$ then $A^2 -b = b$ (replace in the GOOD integer), as desired. $\blacksquare$