Divisibility of $987x^n − F_nx^{16} + F_{n−16}$

Question

If $F_n$ is $n^{th}$ Fibonacci number, and polynomials $P_n(x)$ are defined as $987x^n − F_nx^{16} + F_{n−16}$, prove that for all $n ≥ 1$, $P_n(x)$ is divisible by $x^2−x−1$.

This is from a contest prep class. The hint was to use induction, but it looks to me it is not really the best path.

Case $n=17$, from Wolfram: (amazing fact is that the second factor cannot be factored further, even though its degree is 15!)

Answer 1

Note $\let\phi\varphi$if $\phi=\frac{1+\sqrt5}2$ and $\psi=-\phi^{-1}$ are the roots of $x^2-x-1$, then $F_n=\frac1{\sqrt5}(\phi^n-\psi^n)$ (also for negative $n$).
Observe $P_n(\phi)=F_{16}\phi^n-F_n\phi^{16}+F_{n-16}=\frac1{\sqrt5}((\color{red}{\phi^{16}}-\color{green}{\psi^{16}})\phi^n-(\color{red}{\phi^n}-\color{blue}{\psi^n})\phi^{16}+(\color{green}{\phi^{n-16}}-\color{blue}{\psi^{n-16}}))=0$.
Therefore the conjugate of $\phi$ in $\mathbb Q[\sqrt5]$, $\psi=-\phi^{-1}=\frac{1-\sqrt5}2$ also satisfies $P_n(\psi)=0$. (You could verify this by hand, but I'm too lazy to do that.)
Hence $x^2-x-1=(x-\phi)(x-\psi)$ is a divisor of $P_n(x)$.

Answer 2

$P_n(x)$ satisfies the following recursion:

$$P_n(x) = (1+x)P_{n-1}(x) + (1-x)P_{n-2}(x) - xP_{n-3}(x)$$

Hence by induction it is enough to check that $(x^2-x-1)$ divides it for $n =1,2,3$ which you can verify easily enough.