Register to reply

Does my proof make sense?

by nietzsche
Tags: proof, sense
Share this thread:
nietzsche
#1
Oct9-09, 09:07 PM
P: 186
1. The problem statement, all variables and given/known data

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.

2. Relevant equations



3. The attempt at a solution

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

[tex]
\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*}
[/tex]

where g(x) = c1 and b = (c1a + c0).

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:

[tex]
\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*}
[/tex]

where g(x) = cn+1xn + r(x) + q(x)
and b = k1 + k0.

I think it's right, but I'm always so unsure of myself when it comes to induction.
Phys.Org News Partner Science news on Phys.org
Law changed to allow 'unlocking' cellphones
Microsoft sues Samsung alleging contract breach
Best evidence yet for coronal heating theory detected by NASA sounding rocket
Dick
#2
Oct9-09, 10:15 PM
Sci Advisor
HW Helper
Thanks
P: 25,242
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
#3
Oct9-09, 11:34 PM
P: 186
thanks very much.

Dafe
#4
Dec22-09, 01:40 AM
P: 148
Does my proof make sense?

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

[tex]
\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*}
[/tex]
Dick
#5
Dec22-09, 02:14 AM
Sci Advisor
HW Helper
Thanks
P: 25,242
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
#6
Dec22-09, 03:24 AM
P: 148
Quote Quote by Dick View Post
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 [tex]f(x)[/tex] can be written as [tex](x-a)g(x)+b[/tex] for the [tex]n=1[/tex] case, we can assume that it holds for [tex]k \leq n[/tex], just as you wrote in an earlier post. Then we check to see if the statement holds for the [tex]n+1[/tex] case. I understand that (to the extent I can understand anything).

Quote Quote by Dick View Post
Look at the n=1 case. If you understand that, you understand everything.
[tex]f(x)=c_1x+c_0[/tex]

if [tex](x-a)[/tex] is a factor of [tex]f(x)[/tex] then [tex]f(a)=0[/tex].

[tex]f(\frac{-c_0}{c_1})=c_1(-\frac{c_o}{c_1})+c_0 =0 [/tex]

The Remainder Theorem gives that:
[tex]f(a)=b[/tex], so

[tex]f(x)=(x-(-\frac{c_o}{c_1}))c_1+c_1(-\frac{c_o}{c_1})+c_0[/tex]

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

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
#7
Dec22-09, 09:13 AM
Sci Advisor
HW Helper
Thanks
P: 25,242
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 lets 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
#8
Dec22-09, 11:16 PM
P: 148
Hi,

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

[tex]
\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}
[/tex]

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

[tex]
\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}
[/tex]

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

Thank you for being patient!
Dick
#9
Dec23-09, 09:17 AM
Sci Advisor
HW Helper
Thanks
P: 25,242
That's nice. It was worth waiting for.
Dafe
#10
Dec23-09, 10:50 PM
P: 148
You are too kind, thanks. I feel comfortable with this now.


Register to reply

Related Discussions
Does this make sense? Set Theory, Logic, Probability, Statistics 17
Does this make any sense? Special & General Relativity 2
Does this make any sense? General Physics 1
Um, how does this make sense? General Physics 4