Proving Polynomial Identities Using Induction

[nietzsche]

Homework Statement

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.

Homework Equations

The Attempt at a Solution

Base Case: Let f(x) be a polynomial of degree n = 1. Then:

<br /> \begin{align*}<br /> f(x) &amp;= c_1x+c_0\\<br /> f(x) &amp;= c_1x - c_1a + c_1a + c_0\\<br /> f(x) &amp;= (x-a)c_1 + c_1a + c_0\\<br /> f(x) &amp;= (x-a)g(x) + b<br /> \end{align*}<br />

where g(x) = c₁ and b = (c₁a + c₀).

Let P(n) be the statement that every polynomial function of degree n can be written as f(x) = (x-a)g(x) + b.

Take P(n+1) and assume P(n) is true:

<br /> \begin{align*}<br /> f(x) &amp;= c_{n+1}x^{n+1} + c_{n}x^{n}+...+c_1x + c_0\\<br /> f(x) &amp;= c_{n+1}x^{n+1} + (x-a)q(x) + k_0\\<br /> f(x) &amp;= c_{n+1}x^{n+1} - c_{n+1}x^na + c_{n+1}x^na + (x-a)q(x) + k_0\\<br /> f(x) &amp;= (x-a)(c_{n+1}x^n) + c_{n+1}x^na + (x-a)q(x) + k_0\\<br /> f(x) &amp;= (x-a)(c_{n+1}x^n) + (x-a)r(x) + k_1 + (x-a)q(x) + k_0\\<br /> f(x) &amp;= (x-a)(c_{n+1}x^n + r(x) + q(x)) + k_1 + k_0\\<br /> f(x) &amp;= (x-a)g(x) + b<br /> \end{align*}<br />

where g(x) = c_n+1xⁿ + r(x) + q(x)
and b = k₁ + k₀.

I think it's right, but I'm always so unsure of myself when it comes to induction.

 

[Dick]

That seems ok to me. It might help a bit if you explicitly say why you can make certain substitutions because of the induction hypothesis. But I think it's basically ok. And as a technical point you can't just prove P(n+1) from P(n). c_n might be 0. P(n) should really be "every polynomial function of degree k<=n can be written as f(x) = (x-a)g(x) + b". But that's really just a legal fine point.

 

[nietzsche]

thanks very much.

 

[Dafe]

Hi,
could someone explain how we go from 1. to 2. in the expressions below?
I fail to see how c_{n+1}x^na=(x-a)r(x)+k_1
Thanks.

<br /> \begin{align*}<br /> 1.f(x) &amp;= (x-a)(c_{n+1}x^n) + c_{n+1}x^na + (x-a)q(x) + k_0\\<br /> 2.f(x) &amp;= (x-a)(c_{n+1}x^n) + (x-a)r(x) + k_1 + (x-a)q(x) + k_0\\<br /> \end{align*}<br />

 

[Dick]

It's the induction hypothesis. You assume every polynomial of degree <=n can be written as (x-a)*r(x)+k. Think about it. The OP didn't state this as clearly as should have been done. See if you can do better. Look at the n=1 case. If you understand that, you understand everything. Also think about posting your own threads.

 

[Dafe]

It's the induction hypothesis. You assume every polynomial of degree <=n can be written as (x-a)*r(x)+k. Think about it.

Since we show that f(x) can be written as (x-a)g(x)+b for the n=1 case, we can assume that it holds for k \leq n, just as you wrote in an earlier post. Then we check to see if the statement holds for the n+1 case. I understand that (to the extent I can understand anything).

Look at the n=1 case. If you understand that, you understand everything.

f(x)=c_1x+c_0

if (x-a) is a factor of f(x) then f(a)=0.

f(\frac{-c_0}{c_1})=c_1(-\frac{c_o}{c_1})+c_0 =0

The Remainder Theorem gives that:
f(a)=b, so

f(x)=(x-(-\frac{c_o}{c_1}))c_1+c_1(-\frac{c_o}{c_1})+c_0

I guess this is all good and well if (x-a) is a factor of f(x). But if it isn't then,
f(x)=(x-a)c_1 + c_1(a)+c_0

I've successfully managed to confuse myself.

As for making my own threads, I always read how one should do a proper search before posting. I thought it would be better not to make my own thread about something that has been covered in the past. Will do so in the future though, thanks.

 

[Dick]

n=1. f(x)=c1*x+c0=c1*x-c1*a+c1*a+c0=c1*(x-a)+(c1*a+c0). c1*a+c0 is a number. c1 is a 'polynomial' of degree less than 1. Now let's do n=2. f(x)=c2*x^2+c1*x+c0=c2*x^2-c2*x*a+c2*x*a+c1*x+c0=c2*x*(x-a)+(c2*x*a+c1*x+c0). Since (c2*x*a+c1*x+c0) is a polynomial of degree one, by the induction hypothesis (and as we showed above) it can be written as p(x)(x-a)+b where p(x) has degree <1 (e.g. it's really just a constant). So f(x)=c2*x*(x-a)+p(x)(x-a)+b=(c2*x+p(x))*(x-a)+b. So f(x)=q(x)*(x-a)+b where q(x)=c2*x+p(x) has degree 1. Try doing n=3 explicitly.

Yep, researching is a great idea. In preparation for solving the problem or posting your own thread. I don't necessarily even pay much attention to add ons to ancient posts unless there are my own. If I see some other post with 5+ replies to it, I'll figure the problem is already being dealt with and move on. You'll get more replies faster if it's a new thread.

 

[Dafe]

Hi,

Here's my try at the n=3 case:

<br /> \begin{tabular}{ r c l }<br /> \(f(x)\) &amp; \(=\) &amp; c_3x^3+c_2x^2+c_1x+c_0\) \\<br /> &amp; \(=\) &amp; c_3x^3-c_3x^2a+c_3x^2a+c_2x^2+c_1x+c_0\) \\<br /> &amp; \(=\) &amp; (x-a)c_3x^2+c_3x^2a+c_2x^2+c_1x+c_0\)<br /> \end{tabular}<br />

c_3x^2a+c_2x^2+c_1x+c_0 is a polynomial of degree two, and can, by the induction hypothesis be written as (x-a)p(x)+b.

<br /> \begin{tabular}{ r c l }<br /> \(f(x)\) &amp; \(=\) &amp; (x-a)c_3x^2+(x-a)p(x)+b\) \\<br /> &amp; \(=\) &amp; (x-a)\left(c_3x^2+p(x)\right)+b\) \\<br /> \end{tabular}<br />

q(x)=c_3x^2+p(x) has degree 2, and b has degree 1.

Thank you for being patient!

 

[Dick]

That's nice. It was worth waiting for.

 

[Dafe]

You are too kind, thanks. I feel comfortable with this now.