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:

$$\begin{align*} f(x) &= c_1x+c_0\\ f(x) &= c_1x - c_1a + c_1a + c_0\\ f(x) &= (x-a)c_1 + c_1a + c_0\\ f(x) &= (x-a)g(x) + b \end{align*}$$

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:

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

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.

$$\begin{align*} 1.f(x) &= (x-a)(c_{n+1}x^n) + c_{n+1}x^na + (x-a)q(x) + k_0\\ 2.f(x) &= (x-a)(c_{n+1}x^n) + (x-a)r(x) + k_1 + (x-a)q(x) + k_0\\ \end{align*}$$

 

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

$$\begin{tabular}{ r c l } \(f(x)\) & \(=\) & c_3x^3+c_2x^2+c_1x+c_0\) \\ & \(=\) & c_3x^3-c_3x^2a+c_3x^2a+c_2x^2+c_1x+c_0\) \\ & \(=\) & (x-a)c_3x^2+c_3x^2a+c_2x^2+c_1x+c_0\) \end{tabular}$$

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

$$\begin{tabular}{ r c l } \(f(x)\) & \(=\) & (x-a)c_3x^2+(x-a)p(x)+b\) \\ & \(=\) & (x-a)\left(c_3x^2+p(x)\right)+b\) \\ \end{tabular}$$

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