Find $a$, $b$ such that $x^2 - x -1$ is a factor of $ax^9 + bx^8 + 1$

Question

Find $a$, $b$ such that $x^2 - x -1$ is a factor of $ax^9 + bx^8 + 1$

The second polynomial can be rewritten as $$ax^9 + bx^8 + 1 = f(x)(x^2 - x - 1)$$ The roots of this polynomial are $\frac{1 \pm \sqrt 5}{2}$. Substituting one of these roots in this equation gives us: $$a\left( \frac{1 + \sqrt5}{2}\right)^9 + b\left( \frac{1 + \sqrt 5}{2}\right)^8 + 1 = 0$$

I was able to solve this far, but I gave up because the calculation past this point gets too tedious. The textbook has gone ahead and simplified this to $$2^9 a + 2^8b(\sqrt 5 - 1) + (\sqrt5 - 1)^9 = 0$$ after which it simplifies to (divide by $2^8$ and solve the binomial expression) $$2a + b(\sqrt 5 -1) = 76 - 34\sqrt5$$

Is there a more elegant way to solve this problem? Preferably one that does not include the magical use of a calculator or the evaluation of that ugly binomial expansion?

Answer 1

A polynomial $f(x)$ is a multiple of $x^2-x-1$ (the characteristic polynomial of the Fibonacci sequence) iff $f(\varphi)=f(\bar{\varphi})=0$, with $\varphi=\frac{1+\sqrt{5}}{2}$, $\bar{\varphi}=\frac{1-\sqrt{5}}{2}$ being algebraic conjugates. Since $\varphi^2=\varphi+1$ we have by induction $\varphi^k=F_{k}\varphi+F_{k-1}$ and the same holds for $\bar{\varphi}$. It follows that $ax^9+bx^8+1$ is a multiple of $x^2-x-1$ iff

$$\begin{eqnarray*} 0 &=& a\varphi^9+b\varphi^8+1 = a(34\varphi+21)+b(21\varphi+13)+1\\&=&(34a+21b)\varphi+(21a+13b+1)\end{eqnarray*}$$ and $$ 0 = (34a+21b)\bar{\varphi}+(21a+13b+1). $$ It follows that we must have $21a+13b=-1$ and $34a+21b=0$, so $\color{red}{a=21,b=-34}$ works.
You may also invoke the more general identity $$ (x^2-x-1)\sum_{k=0}^{n}(-1)^{k+1}F_k x^k = (-1)^{n+1}F_n x^{n+2}+(-1)^n F_{n+1} x^{n+1}-x.$$

Answer 2

Put $A = x^2 - x - 1$, $B = ax^9 + bx^8 + 1$ now we want $B/A$ to divide without remainder. We can subtract multiples of $A$ from $B$ to kill off high order terms and see what the remainder would be:

B
- a*x^7*A
= (a + b)*x^8 + a*x^7 + 1

- (a + b)*x^6*A
(2*a + b)*x^7 + (a + b)*x^6 + 1

- (2*a + b)*x^5*A
(3*a + 2*b)*x^6 + (2*a + b)*x^5 + 1

We find

Q = a*x^7 + (a + b)*x^6 + (2*a + b)*x^5
  + (3*a+2*b)*x^4 + (5*a + 3*b)*x^3 + (8*a + 5*b)*x^2
  + (13*a + 8*b)*x + (21*a + 13*b)

R = (34*a + 21*b)*x + 21*a + 13*b + 1

via B - Q A = R

So we need to solve the system

• $34a + 21b = 0$
• $21a + 13b + 1 = 0$

To get no remainder.

Answer 3

Write $ax^9+bx^8+1=(x^2-x-1)\sum\limits_{k=0}^7c_kx^{7-k}$ which gives the initial conditions $c_7=-1$ and $-c_7-c_6=0\implies c_6=1$. Notice that $c_0=a$ and $c_1-c_0=b$ on equating coefficients.

Further, we have $c_i=c_{i-1}+c_{i-2}$ for $i>1$ which is the negative Fibonacci sequence shifted by one. In particular, $c_{7-i}=(-1)^{i+1}F_{i+1}$ so $c_0=F_8$ and $c_1=-F_7$. Hence $a=21$ and $b=-34$.

Answer 4

Consider $$\frac{a x^9+bx^8+1}{x^2-x-1}$$ perform long division to get $$-1+x-2 x^2+3 x^3-5 x^4+8 x^5-13 x^6+21 x^7-(b+34) x^8+x^9 (-a+b+55)+O\left(x^{10}\right)$$ So $b=-34$ and $a=21$ and the result is $$\frac{a x^9+bx^8+1}{x^2-x-1}=-1+x-2 x^2+3 x^3-5 x^4+8 x^5-13 x^6+21 x^7$$

Answer 5

Consider $P(x)= ax^9+bx^8+1$ and $\alpha$ one of the numbers$\frac{1 \pm \sqrt 5}{2}.$

We have equalities:

$\alpha^2$ = $\alpha$ + 1, $\alpha^4$ = 3$\alpha$ + 2, $\alpha^8$ = 21$\alpha$ + 13, $\alpha^9$ = 34$\alpha$ + 21.

(The coefficients to the right of the equations are terms of the Fibonacci sequence)

From $P(\alpha) = 0$ results $a(34\alpha + 21) +b(21\alpha + 13) + 1 =0$ and then $(34a + 21b)\alpha + 21a + 13b + 1 = 0$

If $a$ and $b$ are rational numbers then $$ a = 21, b = -34.$$

Answer 6

Say $c$ and $d$ are zeroes of $x^2-x-1$ then they are zeros of $ax^9+bx^8+1$ too.

Since $c^2 = c+1$ we have $$c^4=c^2+2c+1=3c+2$$ and $$c^8 = 9c^2+12c+4 = 21c+13$$

and finnaly $c^9 = 34c+21$.

So we have $$a(34c+21)+b(21c+13)+1=0$$ or $$\boxed{(34a+21b)c+ (21a+13b+1)=0}$$ Simmilay we have for $d$: $$\boxed{(34a+21b)d+ (21a+13b+1)=0}$$

so if we substract equation and since $c\ne d$ we have $$(34a+21b)(c-d) = 0\implies 34a+21b=0$$

and thus $$21a+13b+1=0$$

Now solve this system and you are done.