$f(n)+f(m) = q^2$ always has a solution

Question

Prove or disprove: Let $f$ be a non-constant polynomial with nonnegative integer coefficients. Then there exist $m,n \in \mathbb{N}$ such that $f(n)+f(m)$ is a perfect square.

I'm just posting this because I noticed the pattern, and I cannot find a counterexample for some reason, although I'm sure there is one somewhere.

Answer 1

This is false; consider $f(x)=x^4$. It is a theorem of Fermat that a sum of two positive fourth powers is never a square, a proof can be found here. If you allow $0\in\Bbb{N}$ then you can instead take $$f(x)=(x+1)^4=x^4+4x^3+6x^2+4x+1.$$

Answer 2

Easier example: let $f(x)=4x+1$. Then $f(n)+f(m)\equiv 2\pmod 4$, but no square can be even but not divisible by $4$.

Answer 3

Inspired by @Wojowu's answer, observe that the only possible quadratic residues mod $8$ are $\{0, 1, 4\}$. Thus, if $$f(x)\equiv_{\pmod 8} \begin{cases} 1\\ 3\\ 5\\ 7 \end{cases} $$ then $f(n)+f(m)$ won't be an perfect square. Examples are $$f(x)=8x+n$$ where $n$ is an odd integer.