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

In summary: Therefore, f has at most 3 roots.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.
  • #1
nietzsche
186
0

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.
 
Physics news on Phys.org
  • #3
aPhilosopher said:
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.
 
Last edited by a moderator:
  • #4
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:

[tex]
f(x) = (x-a_1)(x-a_2)...(x-a_n)(x-a_{n+1})
[/tex]

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.
 
  • #5
You have the idea.

I would write it about like this.

Suppose f is degree [tex]n[/tex] and has [tex]m[/tex] roots. Then [tex] f = (x - a_{1})...(x - a_{m})g[/tex]and [tex](x - a_{1})...(x - a_{m})[/tex] has degree m so [tex]n = m + Deg\ g[/tex].What can you say about the degree of g? What does that tell you about the relationship between m and n?
 
Last edited:
  • #6
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.
 
  • #7
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?
 
Last edited:
  • #8
Dick said:
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.
 
  • #9
nietzsche said:
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.
 
  • #10
Is there something wrong with proving this without induction? It seems much cleaner without the induction.
 
  • #11
Dick said:
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.
 
  • #12
aPhilosopher said:
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. :)
 
  • #13
aPhilosopher said:
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.
 
  • #14
nietzsche said:
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?
 
  • #15
nietzsche said:
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.
 
  • #16
Dick said:
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.
 
  • #17
nietzsche said:
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.
 
  • #18
Where did you get that f must cross the x-axis? What if f(x)= x4+ 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."
 
  • #19
nietzsche said:
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:

[tex]
f(x) = (x-a_1)(x-a_2)...(x-a_n)(x-a_{n+1})
[/tex]

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.
 
  • #20
Let's start over.

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

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?
 
  • #21
aPhilosopher said:
Let's start over.

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

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
 
  • #22
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.
 
  • #23
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-a1) 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.
 
  • #24
I'm not sure what aPhilosopher has in mind, but you were almost there with the induction. Review that again.
 
  • #25
Dick said:
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
 
  • #26
nietzsche said:
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?
 
  • #27
Dick said:
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.
 
  • #28
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)
 
  • #29
ah, you are working from spivak's textbook as well...

i haven't gotten to that part yet, so i wouldn't know
 
  • #30
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?
 
  • #31
on induction in general:

first you prove it for a base case (start the ball rolling).

then you show that IF it holds for n-1, THEN it also holds for n, and then conclude it holds for all natural numbers greater than the number used in the base case (which is usually n = 0 or n = 1).

here, you need a way to reduce the degree of a polynomial by 1. the easiest way to do this is to use the euclidean (or division algorithm), which says we can write a polynomial

f(x) = (x - a)q(x) + r(x), where 0 ≤ deg(r(x)) < deg(x-a) = 1, so r(x) is a constant polynomial.

so f(x) = (x - a)q(x) + r. this means f(a) = (a - a)q(x) + r = 0q(x) + r = r, so we can write this as:

f(x) = (x - a)q(x) + f(a). in particular, if a is a root of f, so that f(a) = 0,

f(x) = (x - a)q(x), and comparing degrees, we see that deg(q(x)) = deg(f(x)) - 1.

now a one degree polynomial x + c has one root, namely -c. so a one degree polynomial has at most 1 root.

if we assume an n-1 degree polynomial has at most n-1 roots, then we let f(x) be any arbitrary n degree polynomial. if f has no roots at all, it certainly has less than n roots.

otherwise, suppose f has a root a. we can write:

f(x) = (x - a)q(x), where deg(q(x)) = n-1, and by our induction hypothesis, has at most n-1 roots. therefore f has the (at most) n-1 roots of q, and the root a, which is at most n roots.
 

1. What is a polynomial?

A polynomial is a mathematical expression consisting of variables and coefficients, combined using basic arithmetic operations such as addition, subtraction, and multiplication. It can also include exponents, but not division or negative exponents.

2. What is the degree of a polynomial?

The degree of a polynomial is the highest exponent of the variable in the expression. For example, in the polynomial 3x^2 + 5x + 1, the degree is 2 because that is the highest exponent of x.

3. How can you determine the number of roots of a polynomial?

By looking at the degree of the polynomial, you can determine the maximum number of roots it can have. For example, a polynomial of degree 3 can have at most 3 roots.

4. What does it mean for a polynomial to have "at most" n roots?

This means that a polynomial may have fewer than n roots, but it cannot have more than n roots. For example, a polynomial of degree 3 may have 2 or 3 roots, but it cannot have 4 or more roots.

5. Why is it important to know the maximum number of roots a polynomial can have?

Knowing the maximum number of roots can help in solving equations involving polynomials. It also provides information about the behavior of the polynomial, such as whether it has any real or complex roots. In addition, it is a fundamental property of polynomials that can be used in various mathematical proofs and applications.

Similar threads

  • Calculus and Beyond Homework Help
Replies
24
Views
615
  • Calculus and Beyond Homework Help
Replies
1
Views
546
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Calculus and Beyond Homework Help
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
14
Views
727
  • Calculus and Beyond Homework Help
Replies
6
Views
963
Back
Top