Polynomial Division (continued from osnarf's problem)

[jimpap]

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.

 

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

 

[SammyS]

Hello,

My problem is the same as osnarf's problem in thread "Polynomial division proof".
But, I would like some further help.

The problem asks : Prove for every f and number a, there are g(x) and number b, that f(x) = (x-a)g(x) + b.
After some steps
a) n=1,
b) Suppose it is true for n=k,
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 tha 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

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:

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.

 

[SammyS]

...

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

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 .

 

[jimpap]

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

 

[SammyS]

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

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.

 

[jimpap]

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.

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?

 

[SammyS]

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?

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 Attempt at a Solution

Proving a polynomial of degree 1 is easy enough for the induction proof.

For proving it for a degree k+1, spivak writes :
suppose the result is true for polynomials of degree <= k.
...

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.

 

[jimpap]

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

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.

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

 

[SammyS]

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

No. They are the very same a_k+1 .

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

 

[jimpap]

No. They are the very same a_k+1 .

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

You mean to try different k for:

f(x)=a_k+1x^k+1+a_kx^k+...+a₁x+a₀,
and
h(x)=f(x)-a_k+1x^k+1
or
h(x)=f(x)-a_k+1(x-a)x^k

 

[SammyS]

You mean to try different k for:

f(x) = a_k+1x^k+1 + a_kx^k +...+ a₁x + a₀,
and
h(x)=f(x)-a_k+1x^k+1
or
h(x) = f(x) - a_k+1(x-a)x^k

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.

 

[jimpap]

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.

I see that the degree is the same as number k and a_k+1x^k+1 is simplified.
But since a_k+1x^k+1 is irrelevant to a_k+1(x-a)x^k, against my original thought,
I can't understand how should I think the h(x) polynomial.

Thank you for your time!

 

[SammyS]

I see that the degree is the same as number k and a_k+1x^k+1 is simplified.
But since a_k+1x^k+1 is irrelevant to a_k+1(x-a)x^k, against my original thought,
I can't understand how should I think the h(x) polynomial.

Thank you for your time!

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}+...\$

 

[jimpap]

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.

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

 

[SammyS]

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

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.

 

[jimpap]

Then either:

1. h(x) is a number (degree zero)
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.

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.

 

[andrewkirk]

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

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?