# Polynomial Division (continued from osnarf's problem)

Tags:
1. Nov 9, 2015

### jimpap

Hello,

My problem is the same as osnarf's problem in thread "Polynomial division proof",
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

Last edited: Nov 9, 2015
2. Nov 9, 2015

### andrewkirk

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.

3. Nov 9, 2015

### SammyS

Staff Emeritus
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:

4. Nov 9, 2015

### SammyS

Staff Emeritus
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 .

5. Nov 10, 2015

### jimpap

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]
a[k+1]ax[k]?

6. Nov 10, 2015

### SammyS

Staff Emeritus
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.

7. Nov 10, 2015

### jimpap

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?

8. Nov 10, 2015

### SammyS

Staff Emeritus
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.

9. Nov 10, 2015

### jimpap

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

10. Nov 10, 2015

### SammyS

Staff Emeritus
No. They are the very same ak+1 .

Write out the two or three highest degree terms of h(x)

11. Nov 10, 2015

### jimpap

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

12. Nov 10, 2015

### SammyS

Staff Emeritus
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.

13. Nov 10, 2015

### jimpap

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.

14. Nov 10, 2015

### SammyS

Staff Emeritus
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.

$\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
15. Nov 10, 2015

### jimpap

Yes it was quite explanatory , I see that the degree is <=k.

16. Nov 10, 2015

### SammyS

Staff Emeritus
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
17. Nov 10, 2015

### jimpap

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.

18. Nov 10, 2015

### andrewkirk

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?