4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.