1. Not finding help here? Sign up for a free 30min 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!

Polynomial Division (continued from osnarf's problem)

Tags:
  1. Nov 9, 2015 #1
    Hello,

    My problem is the same as osnarf's problem in thread "Polynomial division proof",
    https://www.physicsforums.com/threads/polynomial-division-proof.451991/
    But, I would like some further help.

    The problem:
    Prove that for any polynomial function f, and any number a, there is a polynomial function g, and a number b, such that f(x) = (x - a)*g(x) + b for all x.

    After some steps
    a) n=1,
    f(x) = a[1]x+a[0]=a[1](x-a)+(a[0]+a[1]a)
    b) Suppose it is true for n=k,
    f(x)= a[k]x[k]+ a[k-1]x[k-1] +...+ a[1]x+a[0]

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

    c) n=k+1 : f(x) = a[k+1]x[k+1]+ a[k]x[k] +...+ a[1]x+a[0]
    and since we have supposed that f(x) is true for n= k, it turns into a new polynomial :

    h(x) = f(x) - a[k+1](x-a) and has degree <=k?

    I understand f(x), but a[k+1](x-a) is it correct? Did it come from a[k+1]x[k+1]?

    thanks

    Sorry for any inconvenience on reading this thread.
     
    Last edited: Nov 9, 2015
  2. jcsd
  3. Nov 9, 2015 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    First write out very formally and clearly what you can assume for n=k+1 by using your Induction Hypothesis - ie write out the fact that you get by assuming it's true for n=k.

    Once you do that, it may be easier to see how you can prove the required fact for n=k+1. Even if you can't see it, it will be easier for people to help you if you've done the work to define the relevant variables.
     
  4. Nov 9, 2015 #3

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Here is a link to osnarf's thread, which is dated from the year 2010 and has been closed: https://www.physicsforums.com/threads/polynomial-division-proof.451991/

    The wording of the problem there is:
     
  5. Nov 9, 2015 #4

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    As I understand it, this seems to be the very issue osnarf had.

    It looks like Spivak has a typo in the statement:
    ##\displaystyle \ h(x)=f(x)-a_{k+1}(x-a) \ ## and has degree ≤ k .​

    I looks to me that the correct statement is:
    ##\displaystyle \ h(x)=f(x)-a_{k+1}(x-a)x^k \ ## and has degree ≤ k .​

    Of course ƒ(x) is a polynomial of degree k+1, and the resulting polynomial, h(x), has degree less than k+1 .
     
  6. Nov 10, 2015 #5
    Thanks for your instant response.

    But :
    a[k+1](x-a)x[k]
    isn't it equal to:
    a[k+1]x[k+1] - a[k+1]ax[k].

    So, turning from
    a[k+1]x[k+1]
    to
    a[k+1](x-a)x[k]
    wouldn't require to add
    a[k+1]ax[k]?
     
  7. Nov 10, 2015 #6

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    What are we adding a[k+1]ax[k] to ? Does that matter?

    The important thing is that the result is a polynomial having degree of k at most.
     
  8. Nov 10, 2015 #7
    Sorry, I still miss something.
    Yes it became degree of k at most because we subtracted a[k+1]x[k+1].

    So, we should have :

    f(x)-a[k+1]x[k+1] = (x-a)g(x) + b, is this correct, since we have degree at k the most?

    And then

    a[k+1]x[k+1] = a[k+1](x-a)x[k] and we don't take into consideration
    the + a[k+1]ax[k] because it will only add a small amount?
     
  9. Nov 10, 2015 #8

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    No, we don't count on it only being a small amount. It is not discarded at all.

    To quote a bit more from osnarf's thread:
    The resulting polynomial is of degree k or less.

    That polynomial is ##\displaystyle \ h(x)=f(x)-a_{k+1}(x-a)x^k \ ##.

    It is not claimed that this is the same as f(x) minus its leading term.
     
  10. Nov 10, 2015 #9
    If it not claimed that this is the same as f(x) minus its leading term, did we take
    the polynomial h(x)=f(x)-a[k+1](x-a)x[k], meaning
    that f(x) a random polynomial of k+1 power and subtract another polynomial also to the k+1 power?
    So the a[k+1]x[k+1] has nothing to do with a[k+1](x-a)x[k]?
     
  11. Nov 10, 2015 #10

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    No. They are the very same ak+1 .

    Write out the two or three highest degree terms of h(x)
     
  12. Nov 10, 2015 #11
    You mean to try different k for:

    f(x)=ak+1xk+1+akxk+...+a1x+a0,
    and
    h(x)=f(x)-ak+1xk+1
    or
    h(x)=f(x)-ak+1(x-a)xk
     
  13. Nov 10, 2015 #12

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Combine the first and the last expressions.

    Then expand ## \displaystyle \ -a_{k+1}(x-a)x^k \ ## to ## \displaystyle \ -a_{k+1}x^{k+1}+a\cdot a_{k+1}x^k \ ## , and simplify.
     
  14. Nov 10, 2015 #13
    I see that the degree is the same as number k and ak+1xk+1 is simplified.
    But since ak+1xk+1 is irrelevant to ak+1(x-a)xk, against my original thought,
    I can't understand how should I think the h(x) polynomial.

    Thank you for your time!
     
  15. Nov 10, 2015 #14

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Do you see that h(x) is a polynomial with degree of k or less ?

    The inductive step assumes that the result we want to prove "is true for polynomials of degree <= k.", as Spivak puts it.

    Added in Edit:

    ## \displaystyle\ f(x)= a_{k+1}x^{k+1} -a_{k+1}x^{k+1}+a\cdot a_{k+1}x^k +a_zx^x+a_{k-1}x^{k-1}+...\ ##
     
    Last edited: Nov 10, 2015
  16. Nov 10, 2015 #15
    Yes it was quite explanatory , I see that the degree is <=k.
     
  17. Nov 10, 2015 #16

    SammyS

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Then either:
    1. h(x) is a number (degree zero polynomial)
    2. h(x) is a polynomial of degree, n, where 1 ≤ n ≤ k, so that there is a number, c, and a polynomial, p(x), of degree n-1 such that
    ## \displaystyle \ h(x)=(x-a)p(x)+c \ ## .​

    It does not really matter what other details pertain to h(x), only that its degree is k or less.
     
    Last edited: Nov 10, 2015
  18. Nov 10, 2015 #17
    Appreciate your interest. I think spivak's book is pretty difficult. What I was asking clarified at https://www.physicsforums.com/threa...ued-from-osnarfs-problem.842252/#post-5285189.
    And again thank you.
     
  19. Nov 10, 2015 #18

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I see you have now written out the induction hypothesis, but I think maybe you are getting lost in the notation. Using ##f## for both the degree ##k## and the degree ##k+1## polynomial creates confusion.

    Stick with ##f## for the degree ##k## polynomial and call the degree ##k+1## polynomial

    $$F(x)=a_{k+1}x^{k+1}+ a_kx^k +...+ a_1x+a_0\equiv\sum_{j=0}^{k+1}a_jx^j$$

    Then you can write ##F(x)=xf^*(x)+a_0##.

    Writing out ##f^*(x)## is straightforward, and I'll leave that to you.

    Now you can apply the induction hypothesis to ##f^*(x)##, since it has degree ##k##, to write:

    $$f^*(x)=g^*(x)(x-a^*)+b^*$$

    Substitute that into the above formula for ##F(x)## and then rearrange. What do you get?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Polynomial Division (continued from osnarf's problem)
  1. Polynomial division (Replies: 2)

  2. Polynomial Division (Replies: 16)

Loading...