Proof: a polynomial of degree n has at most n roots.

[nietzsche]

Homework Statement

Prove that if f is a polynomial function of degree n, then f has at most n roots, i.e., there are at most n numbers a with f(a) = 0.

Homework Equations

N/A

The Attempt at a Solution

I know that I'm supposed to use induction on the degree of the polynomial. If we assume a polynomial of degree 0, then f(x) is a constant and has no real roots.

Now I don't know how to use induction on that statement. It's very easy to know intuitively but I'm having a lot of trouble formalizing this into a proof. Any hints would be greatly appreciated.

By the way, another question: what if f(x) = 0? How many roots does that have?

Thanks.

 

[aPhilosopher]

This is easy in light of the https://www.physicsforums.com/showthread.php?t=340647" you posted ;)

 

[nietzsche]

This is easy in light of the https://www.physicsforums.com/showthread.php?t=340647" you posted ;)

still not sure if my answer to that problem is right...

but i'll have another look. i was trying to find the relationship between them, but my brain is so tired.

 

[nietzsche]

Hmm... this is what I came up with.

Suppose that f is a polynomial of degree n. Suppose also that f has (n+1) roots. Then:

<br /> f(x) = (x-a_1)(x-a_2)...(x-a_n)(x-a_{n+1})<br />

But this would mean that f is a polynomial of degree (n+1), so f has at most n roots.

It seems kind of incomplete or lacking something.

 

[aPhilosopher]

You have the idea.

I would write it about like this.

Suppose f is degree n and has m roots. Then f = (x - a_{1})...(x - a_{m})gand (x - a_{1})...(x - a_{m}) has degree m so n = m + Deg\ g.What can you say about the degree of g? What does that tell you about the relationship between m and n?

 

[aPhilosopher]

The main problem with the proof you posted is that it only proves that f can't have n + 1 roots! You leave open the possibility that it has n + 2.

 

[Dick]

To say a polynomial of degree zero has roots is a bit of a non sequitur. A polynomial of degree 0 doesn't even have an x in it. I would start the induction with degree 1. Then f(x)=c1*x+c0 with c1 not zero (otherwise it wouldn't be degree 1). That has exactly one root, correct? That takes care of n=1. Now go to n=2. Then f(x) might have NO roots. That's ok, 0<=2. If it has a root 'a' then use your other problem to say f(x)=(x-a)g(x) where g(x) has degree one. So g(x) has one root and the number of roots of f(x) is two. Still ok, 2<=2. That takes care of the degree 2 case. Can you see how to continue from here? What happens at degree 3?

 

[nietzsche]

To say a polynomial of degree zero has roots is a bit of a non sequitur. A polynomial of degree 0 doesn't even have an x in it. I would start the induction with degree 1. Then f(x)=c1*x+c0 with c1 not zero (otherwise it wouldn't be degree 1). That has exactly one root, correct? That takes care of n=1. Now go to n=2. Then f(x) might have NO roots. That's ok, 0<=2. If it has a root 'a' then use your other problem to say f(x)=(x-a)g(x) where g(x) has degree one. So g(x) has one root and the number of roots of f(x) is two. Still ok, 2<=2. That takes care of the degree 2 case. Can you see how to continue from here? What happens at degree 3?

hmm. i have a guess at how to continue but I'm not sure how to formalize it. you can write any polynomial as a product of degree 1 and degree 2 polynomials. so an even polynomial function will have maximum of 2k roots and an odd polynomial will have a maximum of 2k+1 roots.

i'm not sure how to incorporate induction into that.

 

[Dick]

hmm. i have a guess at how to continue but I'm not sure how to formalize it. you can write any polynomial as a product of degree 1 and degree 2 polynomials. so an even polynomial function will have maximum of 2k roots and an odd polynomial will have a maximum of 2k+1 roots.

i'm not sure how to incorporate induction into that.

I didn't ask you finish it. I just asked you happens at degree 3. Don't jump ahead unless you know what you are doing.

 

[aPhilosopher]

Is there something wrong with proving this without induction? It seems much cleaner without the induction.

 

[nietzsche]

I didn't ask you finish it. I just asked you happens at degree 3. Don't jump ahead unless you know what you are doing.

well, I'm sorry... you showed that it was true for the base case of n=1 and n=2 so i thought the next logical step was the induction step...

for f(x) of degree 3:

if f(x) has one root a, then

f(x) = (x-a)g(x)

where g(x) is degree 2.

degree 2 has either 0 or 2 roots, so f(x) has either 1 or 3 roots.

 

[nietzsche]

Is there something wrong with proving this without induction? It seems much cleaner without the induction.

yeah, you could be right. but the way these questions are set up in my textbook makes me feel like the proofs require induction. in any case, i need as much practice on induction as i can get. :)

 

[Dick]

Is there something wrong with proving this without induction? It seems much cleaner without the induction.

If you have a plan to prove it without induction, I would be ok with that. How does it work again? It's a little late here.

 

[Dick]

well, I'm sorry... you showed that it was true for the base case of n=1 and n=2 so i thought the next logical step was the induction step...

for f(x) of degree 3:

if f(x) has one root a, then

f(x) = (x-a)g(x)

where g(x) is degree 2.

degree 2 has either 0 or 2 roots, so f(x) has either 1 or 3 roots.

Almost ok. Why can't f(x) have zero roots? Do you see how the induction is going to go?

 

[aPhilosopher]

yeah, you could be right. but the way these questions are set up in my textbook makes me feel like the proofs require induction. in any case, i need as much practice on induction as i can get. :)

This doesn't require induction at all. The conclusion is that since a polynomial has degree greater than or equal to 0 and we know that n = m + deg g, where n is the degree of f and m is its amount of roots, we then have n >= deg g.

 

[nietzsche]

Almost ok. Why can't f(x) have zero roots? Do you see how the induction is going to go?

f(x) can't have zero roots because it can be either negative or positive, and since f is a polynomial and therefore continuous, it must cross the x-axis at some point.

i'm not sure i see how the induction will work.

 

[Dick]

f(x) can't have zero roots because it can be either negative or positive, and since f is a polynomial and therefore continuous, it must cross the x-axis at some point.

i'm not sure i see how the induction will work.

You shouldn't assume you are working over the real numbers. The theorem is more general. If you are working with only rational numbers, then f(x)=x^3+2 has no roots. There's nothing wrong with that. If f(x) has degree n, then either it has no roots, all fine, 0<=n. Or it has a root and f(x)=(x-a)g(x) where g(x) has degree<n.

 

[HallsofIvy]

Where did you get that f must cross the x-axis? What if f(x)= x⁴+ 1?

The problem is to prove that if f is a polynomial function of degree n, then f has at

most

n roots, right? It looks to me like a proof by contradiction would be simplest.

Suppose f is a polynomial function of degree n and has more than n roots. Can you get a contradiction from that? In his very first response aPhilopher referred to your earlier post that "if x= a is a root of f(x)= 0, then f(x) has x- a as a factor."

 

[nietzsche]

Hmm... this is what I came up with.

Suppose that f is a polynomial of degree n. Suppose also that f has (n+1) roots. Then:

<br /> f(x) = (x-a_1)(x-a_2)...(x-a_n)(x-a_{n+1})<br />

But this would mean that f is a polynomial of degree (n+1), so f has at most n roots.

It seems kind of incomplete or lacking something.

In my earlier post, I tried to do it with contradiction. The induction thing is a bit confusing. I have an intuitive understanding of how to go about doing the proof, but I'm having a lot of trouble piecing it together in a coherent way.

 

[aPhilosopher]

Let's start over.

Suppose f is degree n and has at least m roots. Then f = (x - a_{1})...(x - a_{m})gand (x - a_{1})...(x - a_{m}) has degree m so n = m + Deg\ g.

Do you understand this proof so far?

What can you say about the degree of g? What does that tell you about the relationship between m and n?

 

[nietzsche]

Let's start over.

Suppose f is degree n and has at least m roots. Then f = (x - a_{1})...(x - a_{m})gand (x - a_{1})...(x - a_{m}) has degree m so n = m + Deg\ g.

Do you understand this proof so far?

What can you say about the degree of g? What does that tell you about the relationship between m and n?

Hmm I guess we can say that the degree of g is equal to n - m?

m cannot be > n because that would make g have a negative degree, so it wouldn't be a polynomial?

Thanks for your help btw, appreciate it

 

[aPhilosopher]

No problem. There's a subtlety in the proof though that you should understand. As I first started you off on it last night, it didn't rule out the case that f would have infinite roots. Now, we're saying "suppose that f has at least m roots" as opposed to "suppose that f has m roots." If it has infinite roots, we can assume that for any natural m. We then show that m must be bounded by n, ruling out the infinite case.

 

[nietzsche]

i'm sorry, i really appreciate everyone's help, but I'm still having trouble formalizing this proof. let's say i needed to hand it in for grading. what i want to say is:

a polynomial function f can have at most n roots because a maximum of n factors of the form (x-a₁) can be factored out of f.

it seems so simple to say it in words, but despite all the ideas I've gotten from you guys, I'm still not sure what the best way of expressing it in mathematical terms is.

 

[Dick]

I'm not sure what aPhilosopher has in mind, but you were almost there with the induction. Review that again.

 

[nietzsche]

You shouldn't assume you are working over the real numbers. The theorem is more general. If you are working with only rational numbers, then f(x)=x^3+2 has no roots. There's nothing wrong with that. If f(x) has degree n, then either it has no roots, all fine, 0<=n. Or it has a root and f(x)=(x-a)g(x) where g(x) has degree<n.

the class I'm in is assuming no knowledge of complex numbers, but anyways

If f(x) has degree n+1, then if it has a root, then f(x) = (x-a)g(x) where g(x) has a degree less than n+1...

i'm really confused about where the induction comes in

 

[Dick]

the class I'm in is assuming no knowledge of complex numbers, but anyways

If f(x) has degree n+1, then if it has a root, then f(x) = (x-a)g(x) where g(x) has a degree less than n+1...

i'm really confused about where the induction comes in

We proved if f(x) has degree one, it has one root, right? We also proved if f(x) has degree two it has at most two roots, also right? If f(x) has degree three, then it might have no roots, but if it does have a root then you can write it as f(x)=(x-a)g(x) where g(x) has degree two. g(x) has at most two roots. So f(x) has at most three roots. Assume for your induction hypothesis that a polynomial of degree n has at most n roots. Show that a polynomial of degree n+1 has at most n+1 roots. That's the induction thing, right?

 

[nietzsche]

We proved if f(x) has degree one, it has one root, right? We also proved if f(x) has degree two it has at most two roots, also right? If f(x) has degree three, then it might have no roots, but if it does have a root then you can write it as f(x)=(x-a)g(x) where g(x) has degree two. g(x) has at most two roots. So f(x) has at most three roots. Assume for your induction hypothesis that a polynomial of degree n has at most n roots. Show that a polynomial of degree n+1 has at most n+1 roots. That's the induction thing, right?

ah, thank you. so for every polynomial of degree n, if it has a root, it can be written as
f(x) = (x-a)g(x) where g(x) has at most (n-1) roots.

 

[sallie17]

How do you find a polynomial function of degree n (which is even) with no roots, and a function with degree n (that is odd) with only one root? Thanks. It kinda relates to this problem (in my textbook it is part d)

 

[nietzsche]

ah, you are working from spivak's textbook as well...

i haven't gotten to that part yet, so i wouldn't know

 

[lelybabiii]

well, i never got a formal introduction to indiction so i am working blind. my problem says that i must use induction to prove that a polynomial of degree n can have at most n roots... help?