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

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?