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

1. Sep 26, 2009

### nietzsche

1. The problem statement, all variables and given/known data

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.

2. Relevant equations

N/A

3. 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.

2. Sep 26, 2009

### aPhilosopher

Last edited by a moderator: Apr 24, 2017
3. Sep 26, 2009

### nietzsche

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: Apr 24, 2017
4. Oct 9, 2009

### 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:

$$f(x) = (x-a_1)(x-a_2)...(x-a_n)(x-a_{n+1})$$

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. Oct 9, 2009

### 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})g$$and $$(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?

Last edited: Oct 9, 2009
6. Oct 9, 2009

### 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.

7. Oct 9, 2009

### 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?

Last edited: Oct 9, 2009
8. Oct 9, 2009

### nietzsche

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. Oct 9, 2009

### Dick

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. Oct 9, 2009

### aPhilosopher

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

11. Oct 9, 2009

### nietzsche

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. Oct 9, 2009

### nietzsche

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. Oct 9, 2009

### Dick

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. Oct 9, 2009

### Dick

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

15. Oct 9, 2009

### aPhilosopher

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. Oct 10, 2009

### nietzsche

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. Oct 10, 2009

### Dick

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. Oct 10, 2009

### HallsofIvy

Staff Emeritus
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
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. Oct 10, 2009

### nietzsche

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. Oct 10, 2009

### aPhilosopher

Let's start over.

Suppose f is degree $$n$$ and has at least $$m$$ roots. Then $$f = (x - a_{1})...(x - a_{m})g$$and $$(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?