Does my proof make sense?


by nietzsche
Tags: proof, sense
nietzsche
nietzsche is offline
#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
Better thermal-imaging lens from waste sulfur
Hackathon team's GoogolPlex gives Siri extra powers
Bright points in Sun's atmosphere mark patterns deep in its interior
Dick
Dick is offline
#2
Oct9-09, 10:15 PM
Sci Advisor
HW Helper
Thanks
P: 25,167
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
nietzsche is offline
#3
Oct9-09, 11:34 PM
P: 186
thanks very much.

Dafe
Dafe is offline
#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
Dick is offline
#5
Dec22-09, 02:14 AM
Sci Advisor
HW Helper
Thanks
P: 25,167
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
Dafe is offline
#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
Dick is offline
#7
Dec22-09, 09:13 AM
Sci Advisor
HW Helper
Thanks
P: 25,167
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
Dafe is offline
#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
Dick is offline
#9
Dec23-09, 09:17 AM
Sci Advisor
HW Helper
Thanks
P: 25,167
That's nice. It was worth waiting for.
Dafe
Dafe is offline
#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