1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 26, 2009 #1
    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. jcsd
  3. Sep 26, 2009 #2
    Last edited by a moderator: Apr 24, 2017
  4. Sep 26, 2009 #3
    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
  5. Oct 9, 2009 #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.
     
  6. Oct 9, 2009 #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: Oct 9, 2009
  7. Oct 9, 2009 #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.
     
  8. Oct 9, 2009 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

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

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  11. Oct 9, 2009 #10
    Is there something wrong with proving this without induction? It seems much cleaner without the induction.
     
  12. Oct 9, 2009 #11
    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.
     
  13. Oct 9, 2009 #12
    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. :)
     
  14. Oct 9, 2009 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

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

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Almost ok. Why can't f(x) have zero roots? Do you see how the induction is going to go?
     
  16. Oct 9, 2009 #15
    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.
     
  17. Oct 10, 2009 #16
    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.
     
  18. Oct 10, 2009 #17

    Dick

    User Avatar
    Science Advisor
    Homework Helper

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

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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."
     
  20. Oct 10, 2009 #19
    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.
     
  21. Oct 10, 2009 #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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




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