Add Me!Close Menu Navigation

Polynomial Divisors

Let p(x) = x^2 -3x + 2. Show that for any positive integers  n \ge 2 there exists unique numbers a_n, b_n such that the polynomial  x^n - a_n x - b_n is divisible by p(x)

Let’s first consider the n=3 case, just as an example. We want to show that p(x)|q_3(x), or show q_3(x) as some multiple of p(x).

    \begin{align*} (x^2 -3x + 2)(x+c_0) &= x^3 + c_0x^2 -3x^2 - 3c_0x + 2x + 2c_0 \\ &= x^3 + (c_0-3)x^2 + (2-3c_0)x + 2c_0 \\ c_0 - 3 &= 0 \\ -a_3 &= 2-3c_0 \\ -b_3 &= 2c_0 \end{align*}

Next, we consider the n=4 case

    \begin{align*} (x^2 -3x + 2)(x^2+c_0x+c_1) &= x^4 + c_0x^3 + c_1x^2 - 3x^3 - 3c_0x^2 - 3c_1x + 2x^2 + 2c_0x + 2c_1 \\ &= x^4 + (c_0-3)x^3 + (2 - 3c_0 + c_1)x^2 + (3c_1 + 2c_0)x + 2c_1 \\ c_0 &= 3 \\ c_1 &= 3c_0 - 2 \end{align*}

and finally, just as an example, the n=5 case

    \begin{align*} (x^2 -3x + 2)(x^3+c_0x^2+c_1x+c_2) &= x^5 + c_0x^4 + c_1x^3 + c_2 x^2 - 3x^4 - \\ &3c_0x^3 - 3c_1 x^2 - 3c_2 x + 2x^3 + 2c_0x^2 + 2c_1x + 2c_2 \\ &= x^5 + (c_0 - 3)x^4 + (c_1 - 3c_0 + 2)x^3 + \\& (c_2 - 3c_1 + 2c_0)x^2 + (2c_1 -  3c_2)x + 2c_2 \\ c_0 &= 3 \\ c_1 &= 3c_0 - 2 \\ c_2 &= 3c_1 - 2c_0 \end{align*}

this suggests that (x^2 - 3x + 2)(x^{k-2} + c_0x^{k-3} + c_1x^{k-4} + \cdots) such that

    \begin{align*} c_0 &= 3 \\ c_1 &= 7 \\ c_n &= 3c_{n-1} - 2c_{n-2} \end{align*}

Informally, suppose that P_k \equiv (x^2 - 3x + 2)(x^{k-2} + c_0x^{k-3} + \cdots) = x^k - (3c_{k-3} - 2c_{k-4})x - b_k, then it must be the case that

    \begin{align*} (x^2 - 3x + 2)(x^{k-2} + c_0x^{k-3} + c_1x^{k-4} + \cdots) \underbrace{\times}_{\mathclap{\mbox{don't forget}}} x &= (x^2 - 3x + 2)(x^{k-1} + c_0x^{k-2} + c_1x^{k-3} + \cdots) & \mbox{discharge $P_k$ here}\\ &= x^{k+1} - a_k x^2 - b_k x \\ \intertext{therefore, we only need to show that $c_{k-2}(x^2) = a_kx^2$} a_k &= 3c_{k-3} - 2c_{k-4} \\ &= c_{k-2} \\ &\implies P_{k+1} \end{align*}

This concludes our proof that (x^2 - 3x + 2)(x^{k-2} + c_0x^{k-3} + \cdots), where a_k = c_{k-2}, b_k = 2c_{k-3}. \blacksquare

As an extension, we will further show that c_n = 2c_{n-1}+1. Let P_n \equiv c_n = 2c_{n-1}+1. Immediately, we see that P_1,P_2 holds. Informally, we show that P_{k-1}, P_{k-2} \implies P_k. The body of the inductive steps is as follows

    \begin{align*} c_k &= 3c_{k-1} - 2c_{k-2} \\ &= 3c_{k-1} - (c_{k-1} - 1) \\ &= 2c_{k-1} + 1 \\ &\implies P_k \end{align*}

This concludes our proof that c_n = 2c_{n-1}+1. Sequentially,

    \begin{align*} c_0 &= 3\\ c_1 &= 2(3) + 1 \\ c_2 &= 2^2(3) + 2 + 1 \\ c_3 &= 2^3(3) + 2^2 + 2 + 1 \\ c_k &= 2^{k}(3) + 2^{k-1} + \cdots \\ &= 2^k(2+1) + 2^{k-1} + \cdots \\ &= 2^{k+1} + 2^k + 2^{k-1} + \cdots \\ &= \sum_{i=0}^{k+1} 2^i \\ &= \frac{2^{k+2}-1}{2-1} \\ &= 2^{k+2}-1\ \blacksquare \end{align*}

Posted By Lee

Woosh