Induction proof of Polynomial Division Theorem

  • #1
214
12
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?
 
Last edited:

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2021 Award
15,924
14,342
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?
 
  • Like
Likes Delta2 and CGandC
  • #3
WWGD
Science Advisor
Gold Member
5,715
5,964
Maybe OP can do some reading on Strong and Weak forms of Induction.
 
  • #4
214
12
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?
 
  • #5
510
79
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 lines


The 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.
 
Last edited:
  • Like
Likes CGandC and Delta2
  • #6
214
12
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.
 
  • #7
fresh_42
Mentor
Insights Author
2021 Award
15,924
14,342
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).##
 
  • #8
214
12
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 ## )
 
  • #9
fresh_42
Mentor
Insights Author
2021 Award
15,924
14,342
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.
 
Last edited:
  • #10
214
12
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.
 
  • #11
fresh_42
Mentor
Insights Author
2021 Award
15,924
14,342
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.
 

Related Threads on Induction proof of Polynomial Division Theorem

Top