# Fibonacci sequence in the factorization of certain polynomials having a root at the Golden Ratio

I was playing around with the Golden Ratio $\Phi = \frac{1 + \sqrt 5}{2}$ on Wolfram Alpha and I noticed that if $F_n$ denotes the $n{th}$ Fibonacci number, then the polynomial $P_n(x) = x^n - F_n x - F_{n-1}$ seems always have a root at $\Phi$ (and hence is divisible by the minimal polynomial $f(x) = x^2 - x - 1$ of $\Phi$ )

After testing several $P_n$ I noticed that factoring out the $f(x)$ gave products of the form:

$$P_n(x) = (x^2 - x - 1)(F_1 x^{n-2} + F_2 x^{n-3} + ... + F_{n-2} x + F_{n-1})$$

where the $F_k$ are the $k^{th}$ Fibonacci numbers.

I've been stumped as to why the coefficients of the second factor should list the elements of the Fibonacci sequence like that, and so I'm hoping someone here can provide insight as to why it all seems to work out so nicely.

Distributing the product in the r.h.s. of the factorization formula $$P_n(x) = (x^2 - x - 1)(F_1 x^{n-2} + F_2 x^{n-3} + ... + F_{n-2} x + F_{n-1})$$ gives \begin{align*}(x^2 - x - 1)\left(\sum_{k = 1}^{n - 1} F_k x^{n - 1 - k}\right) &= x^2 \sum_{k = 1}^{n - 1} F_k x^{n - 1 - k} - x \sum_{k = 1}^{n - 1} F_k x^{n - 1 - k} - \sum_{k = 1}^{n - 1} F_k x^{n - 1 - k} \\ &= \sum_{k = 1}^{n - 1} F_k x^{n + 1 - k} - \sum_{k = 1}^{n - 1} F_k x^{n - k} - \sum_{k = 1}^{n - 1} F_k x^{n - 1 - k} \end{align*} Judiciously reindexing to match exponents in $x$ gives that this is $$\sum_{k = -1}^{n - 3} F_{k + 2} x^{n - 1 - k} - \sum_{k = 0}^{n - 2} F_{k + 1} x^{n - 1 - k} - \sum_{k = 1}^{n - 1} F_k x^{n - 1 - k} .$$ If we peel off the terms whose index does not appear in every sum, we can combine the resulting summations and collect like terms: \begin{multline*} \left(F_1 x^n + F_2 x^{n - 1} + \sum_{k = 1}^{n - 3} F_{k + 2} x^{n - 3}\right) - \left(F_1 x^{n - 1} + \sum_{k = 1}^{n - 3} F_{k + 1} x^{n - 3} + F_{n - 1} x \right) \\ - \left(\sum_{k = 1}^{n - 3} F_k x^{n - 3} + F_{n - 2} x + F_{n - 1} \right) \\ = F_1 x^n + (F_2 - F_1) x^{n - 1} + \sum_{k = 1}^{n - 3} (F_{k + 2} - F_{k + 1} - F_k) x^{n - 3} - (F_{n - 1} + F_{n - 2}) x - F_{n - 1} .\end{multline*} We have $F_1 = F_2 = 1$, so the leading term is $x^n$ and the $x^{n - 1}$ term vanishes. The coefficient of the $k$th term of the summation is $F_{k + 2} - F_{k + 1} - F_k$, but this vanishes by the definition of the Fibonacci sequence. The coefficient $F_{n - 1} + F_{n - 2}$ of the $x$ term, again by definition, is equal to $F_n$.

So, as desired, the product is $$\color{#bf0000}{\boxed{(x^2 - x - 1)(F_1 x^{n-2} + F_2 x^{n-3} + ... + F_{n-2} x + F_{n-1}) = x^n - F_n x - F_{n - 1}}} .$$

NB we can view this as a variation of the familiar factorization $$(x - 1)(x^{n - 1} + x^{n - 1} + \cdots + x + 1) = x^n - 1 .$$ More precisely, we can rederive this latter identity by characterizing the sequence $(1, 1, 1, \ldots)$ via the recurrence relation $G_1 = 1$, $G_{k + 1} = G_k$ ($k \geq 1$) and proceeding as above.