Induction proof of Polynomial Division Theorem

[CGandC]

Theorem: Let $f(x), g(x) \in \mathbb{F}[ x]$ by polynomials, s.t. the degree of $g(x)$ is at least $1$. Then: there are polynomials $q(x), r(x) \in \mathbb{F}[ x]$ s.t.
1. $f(x)=q(x) \cdot g(x)+r(x)$
or
2. the degree of $r(x)$ is less than the degree of $g(x)$

Proof ( from lecture notes ):​

Let $k$ be the degree of polynomial $f(x)$ and $m$ the degree of polynomial $g(x)$. It is given that $1 \leq m$. The proof is by induction on $k$.​

Induction basis: $k < m$. Since $f(x)=0 \cdot g(x)+f(x)$ ,​

we can take $r(x) = f(x)$, $q(x) = 0$ and the two requirements requirements of the theorem are satisfied.​

Induction step ( $m \leq k$ ): Suppose the theorem's true for polynomials of degree less than $k$, we'll prove for polynomials of degree $k$.​

We'll write the polynomials $f(x),g(x)$ explicitly:​

$f(x)=a_{0}+a_{1} x+\cdots+a_{k-1} x^{k-1}+a_{k} x^{k}$​

$g(x)=b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}+b_{m} x^{m}$​

where $a_k, b_m$ are different from zero. We'll define a polynomial of the same degree and with the same leading coefficient like $f(x)$:​

$. h(x)=\frac{a_{k}}{b_{m}} x^{k-m} g(x)=\frac{a_{k}}{b_{m}} x^{k-m}\left(\left(b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}\right)+b_{m} x^{m}\right)$​

$=\frac{a_{k}}{b_{m}} x^{k-m}\left(b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}\right)+a_{k} x^{k}$​

Then the degree of $f(x) - h(x)$ is less than $k$. From the induction hypothesis, there are polynomials $q_0(x) , r(x)$ s.t. $f(x)-h(x)=q_{0}(x) \cdot g(x)+r(x)$ and the degree of polynomial $r(x)$ is less than the degree of $g(x)$. We'll move $h(x)$ a side and we'll get​

$f(x)=q_{0}(x) \cdot g(x)+h(x)+r(x)=q_{0}(x) \cdot g(x)+\frac{a_{k}}{b_{m}} x^{k-m} g(x)+r(x)$​

$=\underbrace{\left(q_{0}(x)+\frac{a_{k}}{b_{m}} x^{k-m}\right)}_{q(x) \in \mathbb{F}[ x]} \cdot g(x)+r(x)$​

, as wanted , QED.​

My question:

I don't see how the proof by induction is being done here.
I learned that If I have a claim of the form $\forall n \in \mathbb N . P(n)$ , where $P(n)$ is a claim that depends on $n$, then I can prove by induction by showing that $P(0)$ holds and showing that $\forall n > 0 . P(n) \rightarrow P(n+1)$ holds.

I wrote the theorem in logic as follows: $\forall k,m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . k = deg(f) \land m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$
and the skeleton for the induction proof on $k$ would look as such:
Induction basis: $k = NUMBER$ . we show $\forall m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$. ( I noticed there's already some problem with my logic writing )
Induction step: Let $k \geq NUMBER$ be arbitrary and suppose it is true that $\forall m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$.
We'll prove that $\forall m \in \mathbb N . \forall f(x),g(x) \in F[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$ (again, there is a problem with the logic since we have to prove exactly the same thing as we assumed in the induction hypothesis ).

I read that the induction is being done on the degree of $f(x)$ which is equivalent to doing the induction on the difference between the degrees of $f(x), g(x)$. But still, how does one write in logic the theorem above so as to have it in the form of $\forall n \in \mathbb N . P(n)$ ( where $P(n)$ is some claim that depends on $n$ )? and how would one write the skeleton of the induction proof?

 

[fresh_42]

Theorem: Let $f(x), g(x) \in \mathbb{F}[ x]$ by polynomials, s.t. the degree of $g(x)$ is at least $1$. Then: there are polynomials $q(x), r(x) \in \mathbb{F}[ x]$ s.t.
1. $f(x)=q(x) \cdot g(x)+r(x)$
or
2. the degree of $r(x)$ is less than the degree of $g(x)$

Proof ( from lecture notes ):​

Let $k$ be the degree of polynomial $f(x)$ and $m$ the degree of polynomial $g(x)$. It is given that $1 \leq m$. The proof is by induction on $k$.​

Induction basis: $k < m$. Since $f(x)=0 \cdot g(x)+f(x)$ ,​

we can take $r(x) = f(x)$, $q(x) = 0$ and the two requirements requirements of the theorem are satisfied.​

Induction step ( $m \leq k$ ): Suppose the theorem's true for polynomials of degree less than $k$, we'll prove for polynomials of degree $k$.​

We'll write the polynomials $f(x),g(x)$ explicitly:​

$f(x)=a_{0}+a_{1} x+\cdots+a_{k-1} x^{k-1}+a_{k} x^{k}$​

$g(x)=b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}+b_{m} x^{m}$​

where $a_k, b_m$ are different from zero. We'll define a polynomial of the same degree and with the same leading coefficient like $f(x)$:​

$. h(x)=\frac{a_{k}}{b_{m}} x^{k-m} g(x)=\frac{a_{k}}{b_{m}} x^{k-m}\left(\left(b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}\right)+b_{m} x^{m}\right)$​

$=\frac{a_{k}}{b_{m}} x^{k-m}\left(b_{0}+b_{1} x+\cdots+b_{m-1} x^{m-1}\right)+a_{k} x^{k}$​

Then the degree of $f(x) - h(x)$ is less than $k$. From the induction hypothesis, there are polynomials $q_0(x) , r(x)$ s.t. $f(x)-h(x)=q_{0}(x) \cdot g(x)+r(x)$ and the degree of polynomial $r(x)$ is less than the degree of $g(x)$. We'll move $h(x)$ a side and we'll get​

$f(x)=q_{0}(x) \cdot g(x)+h(x)+r(x)=q_{0}(x) \cdot g(x)+\frac{a_{k}}{b_{m}} x^{k-m} g(x)+r(x)$​

$=\underbrace{\left(q_{0}(x)+\frac{a_{k}}{b_{m}} x^{k-m}\right)}_{q(x) \in \mathbb{F}[ x]} \cdot g(x)+r(x)$​

, as wanted , QED.​

My question:

I don't see how the proof by induction is being done here.
I learned that If I have a claim of the form $\forall n \in \mathbb N . P(n)$ , where $P(n)$ is a claim that depends on $n$, then I can prove by induction by showing that $P(0)$ holds and showing that $\forall n > 0 . P(n) \rightarrow P(n+1)$ holds.

This is correct and the given induction is a bit clumsy. You can set the base for $k=0.$

Or you can do a case distinction first: For $k<m$ there is nothing to do, because we can set $q(x)=0$ and $r(x)=f(x)$.

Now we are left with $k\geq m \geq 1.$ Then an induction base $k=m$ would be reasonable. However, all the following lines are the same as for the case $k>m$ so we would actually write them twice.

The induction step is needed at the end because we decreased the degree of $f(x)$ by possibly only $1,$ so $\deg (f(x)-h(x))$ could still be greater than $m$ and we need the induction step as written.

In a case like this, where we reduce the degree until $k<m,$ we could simply say "and so on until the degree of $f(x)-h_1(x)-h_2(x)-h_{k-m}(x)$ is smaller than $m.$"

It is not really an induction since our process is going down and we have a lower bound, i.e. we have an algorithm that surely comes to an end.

Another way to prove such theorems is by indirect proof and the assumption of a least counterexample:

Assume that $f(x)$ with $k\geq m$ is a counterexample where we cannot find $r(x)$ and $q(x)$ and of minimal degree of all counterexamples. We already know that $k\geq m$ because otherwise we had found such polynomials: $r(x)=f(x)\, , \,q(x)=0.$ Now do the step as written in the lecture note. Then either $f(x)$ is no counterexample (contradiction to the assumption), or $f(x)-h(x)$ is also a counterexample, but of less degree (contradiction to minimality).

I wrote the theorem in logic as follows: $\forall k,m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . k = deg(f) \land m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$
and the skeleton for the induction proof on $k$ would look as such:
Induction basis: $k = NUMBER$ . we show $\forall m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$. ( I noticed there's already some problem with my logic writing )
Induction step: Let $k \geq NUMBER$ be arbitrary and suppose it is true that $\forall m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$.
We'll prove that $\forall m \in \mathbb N . \forall f(x),g(x) \in F[ x] . m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$ (again, there is a problem with the logic since we have to prove exactly the same thing as we assumed in the induction hypothesis ).

I read that the induction is being done on the degree of $f(x)$ which is equivalent to doing the induction on the difference between the degrees of $f(x), g(x)$. But still, how does one write in logic the theorem above so as to have it in the form of $\forall n \in \mathbb N . P(n)$ ( where $P(n)$ is some claim that depends on $n$ )? and how would one write the skeleton of the induction proof?

 

[WWGD]

Maybe OP can do some reading on Strong and Weak forms of Induction.

 

[CGandC]

It is not really an induction since our process is going down and we have a lower bound, i.e. we have an algorithm that surely comes to an end.

If I have to prove a theorem of the form $P(0) \land \forall n \in \mathbb N . ( P(n+1) \rightarrow P(n) )$ , note that what immediately pops into mind is a proof by induction, but it is sort of a reverse induction since in the induction step we would assume $P(n+1)$ and we'd prove $P(n)$. What's this kind of induction called? recursion? dynamic programming?

Another way to prove such theorems is by indirect proof and the assumption of a least counterexample:

I'd prove the theorem by separating to cases as follows:

Assume $k < m$ , [ rest of the proof of theorem goes here ]
Assume $k \geq m$ , [ rest of the proof of theorem goes here ]

Maybe OP can do some reading on Strong and Weak forms of Induction.

I'm familiar with these inductions but the proof by induction of the theorem I brought is a little bit weird, When proving by induction, I'm used to have a theorem to prove as such: $P(0) \land \forall n \in \mathbb N . ( P(n) \rightarrow P(n+1) )$, where the base case to prove is $P(0)$ , the induction step is assuming arbitrary $n \in \mathbb N$ and P(n), then I've to prove $P(n+1)$.
But I couldn't formalize the theorem according to logic with quantifiers so as to see how I could apply the induction in a way that resembles proving theorems of the form $P(0) \land \forall n \in \mathbb N . ( P(n) \rightarrow P(n+1) )$, what would the logical formalization of the theorem be in order to clearly see how I could apply weak/strong induction?

 

[SSequence]

Just commenting on the logical form for the statement/theorem you have written [not commenting on the other parts since I haven't encountered the proof for the given statement before and I would have to spend fair amount of time reading that in OP], I don't understand how you have written it.

For example, here is the theorem (from OP):

Theorem: Let $f(x), g(x) \in \mathbb{F}[ x]$ by polynomials, s.t. the degree of $g(x)$ is at least $1$. Then: there are polynomials $q(x), r(x) \in \mathbb{F}[ x]$ s.t.
1. $f(x)=q(x) \cdot g(x)+r(x)$
or
2. the degree of $r(x)$ is less than the degree of $g(x)$

and the corresponding logical form from OP:

I wrote the theorem in logic as follows: $\forall k,m \in \mathbb N . \forall f(x),g(x) \in \mathbb{F}[ x] . k = deg(f) \land m = deg(g) \land m \geq 1 . \exists q(x) , r(x) \in \mathbb{F}[ x] . f(x) = q(x) \cdot g(x) + r(x) \lor deg(r(x)) <m$
and the skeleton for the induction proof on $k$ would look as such:

Here is my take on this:
$\forall f,g \in \mathbb{F} \,\,[ \,\, deg(g) \geq 1 \rightarrow [\exists q , r \in \mathbb{F} \,\, [(deg(r)<deg(g))$
$\land \forall x \in \mathbb{R} (f(x)=q(x) \cdot g(x)+r(x)) ] \,] \,\, ]$
Edit: Noticed some issues with single line display (probably due to long length), so I split it into two separate linesThe usage of "and" instead of "or" is based upon wikipedia statement of the theorem:
https://en.wikipedia.org/wiki/Polynomial_remainder_theorem

Above I have assumed $\mathbb{F}$ to denote the set of polynomials. Also, the above formula doesn't cover uniqueness of $q$ and $r$ (it seems that would make the logical formula really long), only their existence.

 

[CGandC]

Here is my take on this:
$\forall f,g \in \mathbb{F[ x]} \,\,[ \,\, deg(g) \geq 1 \rightarrow [\exists q , r \in \mathbb{F} \,\, [(deg(r)<deg(g))$
$\land \forall x \in \mathbb{R} (f(x)=q(x) \cdot g(x)+r(x)) ] \,] \,\, ]$

Do you have any idea how a proof by induction would work on this theorem? ( I can't see it simply as a claim of the form $P(0) \land \forall n \in \mathbb N . ( P(n+1) \rightarrow P(n) )$ ). Instead of the base case being $k < m$, I would expect base case such as $k = \_$ , and instead of an induction step of $m \leq k$ I would expect induction step beginning with " Let $k \geq \_$ be arbitrary ... " . The answer by @fresh_42 above helped but I still feel unsure as to how the induction happens or whether the proof is using a different technique that resembles induction.

 

[fresh_42]

Do you have any idea how a proof by induction would work on this theorem? ( I can't see it simply as a claim of the form $P(0) \land \forall n \in \mathbb N . ( P(n+1) \rightarrow P(n) )$ ). Instead of the base case being $k < m$, I would expect base case such as $k = \_$ , and instead of an induction step of $m \leq k$ I would expect induction step beginning with " Let $k \geq \_$ be arbitrary ... " . The answer by @fresh_42 above helped but I still feel unsure as to how the induction happens or whether the proof is using a different technique that resembles induction.

Induction:

Deal with the case $k<m$.
Take $P(k)=P(m)$ as induction base.
Prove $P(k+1) \longrightarrow P(k)$.Algorithm:

DO WHILE $k\geq m$
$P(k+1) \longrightarrow P(k)$
Store $h(x)$
and prove that the degree has strictly decreased
END DO
Deal with $k<m$.
Use all $h(x)$ to write down the final $q(x)$ and $r(x)$.Indirect proof:

Let $k$ be a minimal counterexample, i.e. there is no way to write $f(x)=q(x)\cdot g(x)+r(x)$ with $\deg r(x) <\deg(g(x)$. Then $f(x)-h(x)=q_0(x)g(x)+r(x)$ and $\deg (f(x)-h(x))<k$. Since $k$ was minimal, we have $\deg r(x)\geq \deg g(x)$ contradicting our construction of $r(x).$

 

[CGandC]

I had a small mistake in the theorem I was trying to prove, I had to prove:
Theorem: Let $f(x),g(x) \in \mathbb{F}[ x]$ be polynomials, s.t. $deg( g ) \geq 1$ . Then, there exist unique polynomials $q(x),r(x) \in \mathbb{F}[ x]$ s.t.
$f(x)=q(x)⋅g(x)+r(x)$ and $r(x) = 0 or deg(r) < deg(g)$

In logic, one can write this theorem as:
$\forall f(x),g(x) \in \mathbb{F}[ x]. deg( g ) \geq 1 . \exists q(x),r(x) \in \mathbb{F}[ x]. f(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) )$

( I think the theorem above has a version for uniqueness too for the polynomials $q(x),r(x)$, but I'll prove the current version without uniqueness)

My proof attempt:
Let $g(x) \in F[ x]$ be arbitrary where $x$ is an indeterminate. Suppose $deg(g) \geq 1$. Denote $deg(g) = m$. There exist $b_0,...,b_m \in \mathbb{F}$ s.t. $g(x) = b_0 + ... + b_m \cdot x^m$. We'll prove the following claim by Strong-induction on $deg(f)$,
$\forall f(x) \in \mathbb{F}[ x]. \exists q(x),r(x) \in \mathbb{F}[ x]. f(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) )$,
Base case: $f = 0$. We'll chose $q(x) = 0, r(x) = 0$ and we're finished.
Induction step: Let $f(x) \in \mathbb{F}[ x]$ be arbitrary. Denote $deg(f) = n$. There exist $a_0,...,a_n \in \mathbb{F}$ s.t. $f(x) = a_0 + ... + a_n \cdot x^n$.
( induction assumption: ) Suppose that $\forall \hat{f}(x) \in \mathbb{F}[ x] . deg( \hat{f} ) < n . \exists q(x),r(x) \in \mathbb{F}[ x]. \hat{f}(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) )$.
We'll prove that $\exists q(x),r(x) \in \mathbb{F}[ x]. f(x)=q(x)⋅g(x)+r(x) \land ( r(x) = 0 \lor deg(r)< deg(g) )$.
If $n < m$ then we'll chose $r = f , q = 0$ and we'll have $f(x) = 0 \cdot g(x) + f(x) = f(x)$ and we're finished.
If $n \geq m$ then we'll look at $h(x) = \frac{a_n}{b_m} \cdot x^{n-m} \cdot g(x)$, notice that $deg( f - h) < n$ and from the induction assumption there exist $q(x),r(x) \in \mathbb{F}[ x]$ s.t. $f(x) - h(x) = q(x) \cdot g(x) + r(x)$, meaning $f(x) = q(x) \cdot g(x) + h(x) + r(x) =q(x) \cdot g(x) + ( \frac{a_n}{b_m} \cdot x^{n-m} \cdot g(x) ) + r(x)$
$= ( q(x) + \frac{a_n}{b_m} \cdot x^{n-m} )\cdot g(x) + r(x)$ and we're finished.

What do you think? ( The induction assumption was only used in the case $n \geq m$ )

 

[fresh_42]

What do you think?

Looks correct. I couldn't see a mistake.

Uniqueness is in general not necessary. It could be tricky to prove. From
$$
f(x)=q(x)g(x)+r(x)=p(x)g(x)+s(x) \Longrightarrow (p(x)-q(x))g(x)+(s(x)-r(x))=0
$$
we only get that the highest coefficients of $p(x)$ and $q(x)$ are equal. I'm not sure whether induction works since the coefficients less than $m=\operatorname{deg}g$ could be anything.

More interesting than uniqueness are the cases in which we haven't a field, rather only a ring with a valuation function.

 

[CGandC]

Here is a proof for uniqueness ( no need for induction here ):

[ We proved existence of $q ,r \in \mathbb{F}[ x]$ s.t. $f(x) = q(x) \cdot g(x) + r(x)$ where $r = 0$ or $deg(r) < deg(g)$ ]
Let $p(x), s(x) \in \mathbb{F} [ x]$ be arbitrary such that $f(x) = p(x) \cdot g(x) + s(x)$.
We have that $f(x) = q(x) \cdot g(x) + r(x) = p(x) \cdot g(x) + s(x) \Longrightarrow (p(x)-q(x))g(x) = (r(x)-s(x))$.
If $p - q \neq 0$ then the polynomial $(p(x)-q(x))g(x)$ has degree higher or equal to $g(x)$, whilst note that the polynomial $(r(x)-s(x))$ is either zero or has degree less than $g(x)$, hence in the equation $(p(x)-q(x))g(x) = (r(x)-s(x))$ we get a contradiction since the left-hand side is a polynomial with degree higher than the righthand side. Hence $p = q$. This means that $r = s$ and we're finished.

 

[fresh_42]

Here is a proof for uniqueness ( no need for induction here ):

[ We proved existence of $q ,r \in \mathbb{F}[ x]$ s.t. $f(x) = q(x) \cdot g(x) + r(x)$ where $r = 0$ or $deg(r) < deg(g)$ ]
Let $p(x), s(x) \in \mathbb{F} [ x]$ be arbitrary such that $f(x) = p(x) \cdot g(x) + s(x)$.
We have that $f(x) = q(x) \cdot g(x) + r(x) = p(x) \cdot g(x) + s(x) \Longrightarrow (p(x)-q(x))g(x) = (r(x)-s(x))$.
If $p - q \neq 0$ then the polynomial $(p(x)-q(x))g(x)$ has degree higher or equal to $g(x)$, whilst note that the polynomial $(r(x)-s(x))$ is either zero or has degree less than $g(x)$, hence in the equation $(p(x)-q(x))g(x) = (r(x)-s(x))$ we get a contradiction since the left-hand side is a polynomial with degree higher than the righthand side. Hence $p = q$. This means that $r = s$ and we're finished.

From $p-q\neq 0$ and the degree consideration, we can only conclude that the leading terms in $p$ and $q$ are equal so that they vanish. I do not see why the lower terms should be equal, too.