Proof that nth-degree polynomial has n roots by induction

11 replies · 3K views · last reply
PcumP_Ravenclaw
Messages
105
Reaction score
4
Dear all,
I am trying to understand the fundamental theorem of algebra from the text (Alan F. Beardon, Algebra and Geometry) attached in this post. I have understood till the first two attachments and my question is from the 3rd attachment onwards.

I will briefly describe what is said in the first two attachments. In the first two attachments, it is stated that for a nth order complex polynomial like
## p(z) = a_{0} + a_{1}z + ... + a_{n}z^n ##
there are n distinct complex solutions.

The fundamental theorem of Algebra proves this fact. It also says that this same equation can be written in another format like

## p(z) = a_{n}(z - z_{1}) ... (z - z_{n}) ##

so that each z1, z2, ..., zn are complex solutions.

We start off by saying that a complex polynomial like ## p(z) ## has at least a single root.
We will use topological arguments to prove this.

If ## p(z) ## as in the first equation above were written in complex form with z substituted by ## z = re^{iθ} ## it would be

## p(z) = a_{0} + (a_{1}r^{iθ}) + (a_{2}r^2e^{i2θ}) + ... + (a_{n}r^ne^{inθ}) ##

In the above equation ## a_{0} ## is a non-zero term so that p(0) is not 0 but why z=0 be a root?
If r value in ## re^{iθ} ## is very big then the ##(a_{n}r^ne^{inθ}) ## term will dominate and it will be a big circle that has rotated n times. if the r value is small then the constant ## a_{0} ## term will dominate. and the small r will form a small circle around it as shown in the second figure in the second attachment.

Now, If the radius, r increases gradually every 0 to 2pi rotation. For some r and θ, p(z) will intersect the origin, 0 + 0i.

This will be the first root of p(z). I see that the magnitude of the origin from ## a_{0} ## will be fixed and the only changes are going to be in the angle θ. so the next solutions will be the angle at which p(z) intersects the 2nd time, 3rd time and so on. So r is fixed and only θ changes for each root? Am I right about this??

Next, in the 3rd paragraph of the third attachment. We use proof by induction to show that if there is one root for n = 1. then there are roots from 1 to n for n > 1. Right??

n = 1 is the anchor step. It is correct when we substitute in p(z) = 0 below.

## p(z) = a_{0} + (a_{1}r^{iθ}) = a_{n}(z - z_{1}) ##

so the single solution for n =1 must be ## r^{iθ} = - a_{0} / a_{1} ## similarly ## z = z_{1} ## from above equation.

by putting n = n + 1, we must show that the R.H.S = L.H.S in Induction step of the proof but I don't know how to do it. :( can anyone show me?? thanks..

How did they arrive at the formula ## p(z) - p(z_{1}) = \sum\limits_{k=1}^n a_{k}(z^k - z_{1}^k) ##

In the above equation, z_{1} is the first root of p(z) when n = 1 so why is it in the above equation??

Danke..
 
Attachments
  • Textbook page titled 3.7 The Fundamental Theorem of Algebra, with key terms highlighted in yellow. It defines a polynomial of degree n, p(z) = a0 + a1 z + ... + an z^n (3.7.1), and states the theorem that p(z) = an(z - z1)...(z - zn) (3.7.2).
    FTA1.JPG
    77 KB · Views: 524
  • Textbook page excerpt on the fundamental theorem of algebra, with highlighted text about applying p(z) to circles centred at the origin and the formula p(z) = a0 + a1z + ... + z^n, n ≥ 1, a0 ≠ 0.
    fta2.JPG
    50.6 KB · Views: 563
  • Printed textbook page of mathematical prose with yellow highlighting, discussing a polynomial p(z) with non-zero constant term, a curve C_r winding around the origin, and an induction proof that a degree n polynomial factorises into n linear factors.
    FTA3.JPG
    76.8 KB · Views: 519
  • Textbook page 50 with yellow highlighting: text on factoring a complex polynomial p(z) = c(z - x1)...(z - xm)(z - z1)(z - z1bar)...(z - zk)(z - zkbar), with real zeros and conjugate pairs of complex zeros.
    FTA4.JPG
    62.6 KB · Views: 566
  • Textbook page with yellow highlighting: text on real quadratic polynomials and partial fractions, Theorem 3.7.1 on polynomials agreeing at n+1 points, its proof, and the start of Cotes's result PA1.PA2...PAn = 1 - x^n (3.7.3).
    FTA5.JPG
    69.5 KB · Views: 561
  • Printed textbook page, page 51, section 3.7 The Fundamental Theorem of Algebra, showing the product identity PA1.PA2...PAn equal to the modulus of (x-1)(x-w)...(x-w^(n-1)), then (z-1)(z-w)...(z-w^(n-1)) = z^n - 1, and text about equating moduli to obtain (3.7.3).
    FTA6.JPG
    22.6 KB · Views: 573
PcumP_Ravenclaw said:
How did they arrive at the formula ## p(z) - p(z_{1}) = \sum\limits_{k=1}^n a_{k}(z^k - z_{1}^k) ##
..
You can rewrite the right hand side as ## \sum\limits_{k=1}^n a_{k}(z^k) - \sum\limits_{k=1}^n a_{k}(z_{1}^k)##
 
  • Like
Likes   Reactions: PcumP_Ravenclaw
so This is equivalent to ## p(z) = p(z_{1}) + \sum\limits_{k=1}^n a_{k}(z^k) - \sum\limits_{k=1}^n a_{k}(z_{1}^k) ##. When this equation is compared with ## p(z) = a_{0} + a_{1}z + ... + a_{n}z^n ## The term ## a_{0} ## equals ##p(z_{1}) - \sum\limits_{k=1}^n a_{k}(z_{1}^k)## and the terms ## a_{1}z + ... + a_{n}z^n ## equals ## \sum\limits_{k=1}^n a_{k}(z^k) ## ?
 
PcumP_Ravenclaw said:
so This is equivalent to ## p(z) = p(z_{1}) + \sum\limits_{k=1}^n a_{k}(z^k) - \sum\limits_{k=1}^n a_{k}(z_{1}^k) ##. When this equation is compared with ## p(z) = a_{0} + a_{1}z + ... + a_{n}z^n ## The term ## a_{0} ## equals ##p(z_{1}) - \sum\limits_{k=1}^n a_{k}(z_{1}^k)## and the terms ## a_{1}z + ... + a_{n}z^n ## equals ## \sum\limits_{k=1}^n a_{k}(z^k) ## ?

Yes you are correct . But more simply, the ## a_{0}'s## cancel and you are just left with the difference of terms of degree 1 and higher.

Notice that the right hand side has a factor of ##z-z_{1}##
 
Last edited:
  • Like
Likes   Reactions: PcumP_Ravenclaw
PcumP_Ravenclaw said:
it is stated that for a nth order complex polynomial like
## p(z) = a_{0} + a_{1}z + ... + a_{n}z^n ##
there are n distinct complex solutions.

It doesn't say "distinct".
 
  • Like
Likes   Reactions: PcumP_Ravenclaw
I scribbled some numbers and tried to understand the connection between
## p(z) = a_{0} + a_{1}z + ... + a_{n}z^n ## and ## p(z) = p(z_{1}) + \sum\limits_{k=1}^n a_{k}(z^k) - \sum\limits_{k=1}^n a_{k}(z_{1}^k) ## . I have attached my work in this post. So it seems to me that the only solution for ## p(z) - p(z_{1}) = \sum\limits_{k=1}^n a_{k}(z^k - z_{1}^k) ## is ## z_{1} ##. what about the remaining n - 1 solutions??
 
Attachments
  • Handwritten derivation: P(z) = a0 + a1z + a2z^2 + ... + anz^n is rewritten by factoring out or expanding the sum of ak(z^k - z1^k), giving a1(z - z1) + a2(z^2 - z1^2) + ... + an(z^n - z1^n) with a0 replaced, and notes that z1 is a common factor of each term.
    fundamental.jpg
    43.7 KB · Views: 517
Once you factor out ## z - z_{1}## , ## a_{1} ## will be a constant
 
  • Like
Likes   Reactions: PcumP_Ravenclaw
PcumP_Ravenclaw said:
## p(z) = a_{0} + a_{1}r^{iθ} + a_{2}r^2e^{i2θ} + ... + a_{n}r^ne^{inθ}##

In the above equation ##a_{0}## is a non-zero term so that p(0) is not 0 but why z=0 be a root?
If r value in re^{iθ} is very big then the (anrneinθ)(a_{n}r^ne^{inθ}) term will dominate and it will be a big circle that has rotated n times. if the r value is small then the constant a0 a_{0} term will dominate. and the small r will form a small circle around it as shown in the second figure in the second attachment.

Now, If the radius, r increases gradually every 0 to 2pi rotation. For some r and θ, p(z) will intersect the origin, 0 + 0i.

This will be the first root of p(z). I see that the magnitude of the origin from a0 a_{0} will be fixed and the only changes are going to be in the angle θ. so the next solutions will be the angle at which p(z) intersects the 2nd time, 3rd time and so on. So r is fixed and only θ changes for each root? Am I right about this??
 
Last edited by a moderator:
PcumP_Ravenclaw said:
## p(z) = a_{0} + a_{1}r^{iθ} + a_{2}r^2e^{i2θ} + ... + a_{n}r^ne^{inθ}##
In the above equation ##a_{0}## is a non-zero term so that p(0) is not 0 but why z=0 be a root?
Why do you think that z = 0 should be a root?
 
PcumP_Ravenclaw said:
This will be the first root of p(z). I see that the magnitude of the origin from ## a_{0} ## will be fixed and the only changes are going to be in the angle θ. so the next solutions will be the angle at which p(z) intersects the 2nd time, 3rd time and so on. So r is fixed and only θ changes for each root? Am I right about this??
No. Remember that ##r## is the modulus of ##z##. If ##r## were fixed, that means all of the roots would be the same distance from the origin. Clearly, that can't be true in general, e.g., p(z) = (z-2)(z-1).

Suppose you let ##p(z) = a_0 + q(z)##. For every root of p(z), it's must be that ##q(z)=-a_0##. So, for instance, ##q(z_1) = q(r_1e^{i\theta_1})=-a_0## and ##q(z_2) = q(r_2 e^{i\theta_2}) = -a_0##. It doesn't follow, however, that ##r_1 = r_2##. You've confused ##\|q(z)\|##, which is fixed for all the roots of p(z), with ##r=\|z\|##.

How did they arrive at the formula ## p(z) - p(z_{1}) = \sum\limits_{k=1}^n a_{k}(z^k - z_{1}^k) ##
I'm not sure you understood what lavinia said in post 4. You have
\begin{align*}
p(z) &= a_0 + a_1 z + \cdots + a_n z^n \\
p(z_1) &= a_0 + a_1 z_1 + \cdots + a_n z_1^n
\end{align*} What do you get when you subtract the second equation from the first?
 
If you start out with the fact that every complex polynomial has at least a single root (say z = a0), then you can rewrite your polynomial p(z) as (z - a0)*p1(z), where the degree of p1 is one less than the degree of p. Now p1 is also a polynomial and will therefore have at least a single root (say z = a1). Continue this argument until the resulting pn has degree 1, and the theorem is proved.
 
PcumP_Ravenclaw said:
Dear all,
I am trying to understand the fundamental theorem of algebra from the text (Alan F. Beardon, Algebra and Geometry) attached in this post. I have understood till the first two attachments and my question is from the 3rd attachment onwards.

I will briefly describe what is said in the first two attachments. In the first two attachments, it is stated that for a nth order complex polynomial like
## p(z) = a_{0} + a_{1}z + ... + a_{n}z^n ##
there are n distinct complex solutions.
Was this typo? While any nth degree polynomial equation has n complex solutions, in general they are NOT all distinct.