Given the polynomial
$$p(x,y)=2y^4x+y^3x^2-2y^2x^3-y^5-yx^4+2y$$
how would one prove that its positive values of $p$ (for $x=1,2,...,y=1,2...$) coincide with the Fibonacci numbers?
Tried something like $p(x-1, y-2)$ or $p(x-2, y-2) + p(x-1, y-1)$. But it didn't work, of course.
I've figured out that $p(f_{n-1}, f_n) = f_n$. So, Induction, perhaps?
I don't think it has anything to do with Fibonacci Polynomials.
This is a perhaps surprising, really elegant, and not-quite-elementary result due to James Jones.
The key is to rewrite your polynomial appropriately, noting that $$ \begin{align}p(x,y)&=2y^4x+y^3x^2-2y^2x^3-y^5-yx^4+2y\\ &=y(2y^3x+y^2x^2-2yx^3-y^4-x^4+2)\\&=y(2-(y^4-2y^3x-y^2x^2+2yx^3+x^4))\\&=y(2-((y^4-2y^3x+y^2x^2)-2(y^2x^2-yx^3)+x^4))\\&=y(2-(y^2-yx-x^2)^2).\end{align} $$
From this it follows that, for $x,y$ positive, $p(x,y)>0$ if and only if $(y^2-yx-x^2)^2<2$, which means that if, in addition, $x,y$ are integers, then we must have $|y^2-yx-x^2|=0$ or $1$. The case where the expression is $0$ is handled in this question.
For the interesting case, I refer you to Jones's paper. In lemma 1, he shows that $f_{n+1}^2-f_{n+1}f_n-f_n^2=\pm1$. This is easily established by induction, and shows that all positive Fibonacci numbers are in the range of $p$ when its arguments are restricted to positive integers. Lemmas 2 and 3 prove the converse: If $x,y$ are positive integers and
For the second, note that if $y^2-yx-x^2=-1$, then $(x+y)^2-(x+y)y-y^2=1$, so, arguing by induction, it suffices to consider the first case, which is then handled elegantly by Jones via induction and clever inequalities.
The reference (available online!) is
The result is related to Hilbert's tenth problem, the solution of which required establishing several similar results.