Mixing
Prove all roots of $p_n(x)-x$ are real and distinct
$begingroup$
Given a polynomial series ${p_n(x)}_{n=1}^{infty}$ in $mathbb{R}[X]$ with initial value $p_1(x)=x^2-2$. And $p_k(x)=p_1(p_{k-1}(x))=p_{k-1}(x)^2-2,;k=2,3,cdots$.
Prove that for each integer $n$, all roots of $p_n(x)-x$ are real and distinct.
This is an problem in my linear algebra textbook.
I tried to figure out the relation of the roots between adjacent polynomial, but I couldn't find any useful result. Also I thought if it could be solved by induction, but it seems impracticable.
linear-algebra polynomials roots
asked Jan 20 at 4:36
Tao XTao X
815
$endgroup$
add a comment |
$begingroup$
Given a polynomial series ${p_n(x)}_{n=1}^{infty}$ in $mathbb{R}[X]$ with initial value $p_1(x)=x^2-2$. And $p_k(x)=p_1(p_{k-1}(x))=p_{k-1}(x)^2-2,;k=2,3,cdots$.
Prove that for each integer $n$, all roots of $p_n(x)-x$ are real and distinct.
This is an problem in my linear algebra textbook.
I tried to figure out the relation of the roots between adjacent polynomial, but I couldn't find any useful result. Also I thought if it could be solved by induction, but it seems impracticable.
linear-algebra polynomials roots
asked Jan 20 at 4:36
Tao XTao X
815
$endgroup$
3
$begingroup$
The relationship between the roots of the successive polynomials is clearer if you write $p_k(x)=p_{k-1}(p_1(x))$ instead.
$endgroup$
– Eric Wofsey
Jan 20 at 5:18
add a comment |
$begingroup$
Given a polynomial series ${p_n(x)}_{n=1}^{infty}$ in $mathbb{R}[X]$ with initial value $p_1(x)=x^2-2$. And $p_k(x)=p_1(p_{k-1}(x))=p_{k-1}(x)^2-2,;k=2,3,cdots$.
Prove that for each integer $n$, all roots of $p_n(x)-x$ are real and distinct.
This is an problem in my linear algebra textbook.
I tried to figure out the relation of the roots between adjacent polynomial, but I couldn't find any useful result. Also I thought if it could be solved by induction, but it seems impracticable.
linear-algebra polynomials roots
asked Jan 20 at 4:36
Tao XTao X
815
$endgroup$
Given a polynomial series ${p_n(x)}_{n=1}^{infty}$ in $mathbb{R}[X]$ with initial value $p_1(x)=x^2-2$. And $p_k(x)=p_1(p_{k-1}(x))=p_{k-1}(x)^2-2,;k=2,3,cdots$.
Prove that for each integer $n$, all roots of $p_n(x)-x$ are real and distinct.
This is an problem in my linear algebra textbook.
I tried to figure out the relation of the roots between adjacent polynomial, but I couldn't find any useful result. Also I thought if it could be solved by induction, but it seems impracticable.
linear-algebra polynomials roots
linear-algebra polynomials roots
asked Jan 20 at 4:36
Tao XTao X
815
asked Jan 20 at 4:36
Tao XTao X
815
asked Jan 20 at 4:36
Tao XTao X
815
asked Jan 20 at 4:36
Tao XTao X
815
asked Jan 20 at 4:36
Tao XTao X
815
815
3
$begingroup$
The relationship between the roots of the successive polynomials is clearer if you write $p_k(x)=p_{k-1}(p_1(x))$ instead.
$endgroup$
– Eric Wofsey
Jan 20 at 5:18
add a comment |
3
$begingroup$
The relationship between the roots of the successive polynomials is clearer if you write $p_k(x)=p_{k-1}(p_1(x))$ instead.
$endgroup$
– Eric Wofsey
Jan 20 at 5:18
3
3
$begingroup$
The relationship between the roots of the successive polynomials is clearer if you write $p_k(x)=p_{k-1}(p_1(x))$ instead.
$endgroup$
– Eric Wofsey
Jan 20 at 5:18
$begingroup$
The relationship between the roots of the successive polynomials is clearer if you write $p_k(x)=p_{k-1}(p_1(x))$ instead.
$endgroup$
– Eric Wofsey
Jan 20 at 5:18
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Hint:
Observe that $-2 le P_1(x) le 2$ for all $-2le xle 2$ and both its roots lie in the same interval. This property becomes obvious by substitution $x=2cos t$ which maps interval $tin[0,pi]$ onto $xin[-2,2]$.
We have:
$$
P_1(2cos t)=(2cos t)^2-2=4frac{1+cos 2t}{2}-2=2cos 2t.
$$
Similarly by induction:
$$
P_n(2cos t)=2cos 2^n t.
$$
Thus the polynomial $P_n(x)$ has exactly $2^{n}$ roots on the interval $(-2,2)$:
$$
xi_k=2cosfrac{2k-1}{2^{n+1}}pi,quad k=1dots 2^n.
$$
Besides the polynomial has alternating $2^{n-1}+1$ maxima $P(xi_k^text{max})=2$ at
$$
xi_k^text{max}=2cosfrac{2k}{2^n}pi,quad k=0dots 2^{n-1}
$$
and $2^{n-1}$ minima $P(xi_k^text{min})=-2$ at
$$
xi_k^text{min}=2cosfrac{2k-1}{2^n}pi,quad k=1dots 2^{n-1}.
$$
Note that the maxima at $x=-2$ and $x=2$ are not necessary the extreme points of the polynomial $P_n(x)$, they are just its values at the boundaries of the interval $[-2,2]$.
Note also that as the order of the polynomial $P_n(x)$ is $2^n$ we have found all the roots of the polynomial.
What remains is to prove that the function $Q(x)=x$ intersects the curve described above in exactly $2^n$ points. For this observe that on the interval $(-2,2)$ the graph of $P_n(x)$ consists of $2^n$ parts connecting adjacent maxima and minima. (Note that in fact $Q(x)$ can be any polynomial of order less than $2^n$ such that $-2<Q(x)<2$ for any $-2<x<2$.)
answered Jan 22 at 11:56
useruser
4,96611030
$endgroup$
add a comment |
$begingroup$
Lemma; Let $n geq 2$; If $p_{n}(x)$ has a local minima it is $-2$. If $p_{n}(x)$ has a local maxima it is $2$. Local minima with $x>0$ occurs $2^{n-2}$ times, Local minima with $x<0$ occurs $2^{n-2}$ times, Local maxima with $x<0$ occurs $2^{n-2} -1$ times and finally Local maxima with $x>0$ occurs $2^{n-2}-1$ times. Local maxima occurs at $x=0$
Proof; Differentiating $p_{n}$ we find that
$p_{n}'(x) = 2p_{n-1}(x)(p_{n-1}'(x))$
Hence
(1) $p_{n}'(x) = 2p_{n-1}(x)(2p_{n-2}(x))...(2p_{1}(x))(2x)$
To be a local minima or maxima one has $p_{n}'(x) = 0$. By looking at (1) we see that some $p_{n-j}(x)$ is $0$ or $x=0$. If $p_{n-1}(x)$ is 0 then $p_{n}(x)$ is $-2$. If some $p_{n-j}(x)$ for $jgeq 2$ is $0$ (just define $p_{0}(x) = x$) then $p_{n}(x) = 2$. So if (x,p_n(x)) is a turning point p_n(x) is $pm 2$. Also note that there are no double roots as if $p_h(x) = 0$ then for any $a >0$ $p_{h+a}(x) = 2$ or $-2$
Now note that each $p_n(x)$ has $2^{n}$ distinct roots. So we can label the roots in an increasing order $c_{1} < c_{2} ...< c_{2^n}$. Observe that between any two successive roots $c_{u}$ and $c_{u+1}$ one has a turning point.
We claim that between any successive roots there is exactly one turning point. To see this suppose that there is an interval $[c_u,c_{u+1}]$ that contains atleast two turning points; hence there are at least $2^n$ turning points in $[c_{1},c_{2^n}]$ but there can only be at most $2^n-1$ turning points (as degree of $p_n(x)$ is $2^{n}$). Combining this information and the information in the previous paragraph we have that in an interval $[c_{u}, c_{u+1}]$
; $p_n(x)$ attains exactly one of the following;
(I) A local minima of -2
(II) A local maxima of 2
Going all the way back and looking at (1) (the equation above) (I) occurs exactly when $p_{n-1}(x) = 0$ which has $2^{n-1}$ distinct roots; half positive and half negative (even function). (II) occurs exactly when some $p_{n-j}(x) =0$ for some $j geq 2$ which happens at $2^{n-1} - 1$ distinct places with one of them being $0$.
We will use the observation that the roots of $p_n(x)$ satisfy $|x| < 2$ to finish the proof.
Now consider each of the $2^{n-2} -1$ type (II) intervals $[c_{u},c_{u+1}]$ with $c_{u} > 0$ we can split this interval into two intervals $[c_{u},d]$ and $[d,c_{u+1}]$ where $p_n(d) = 2$ applying intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ we find that $g_n(x)$ contains two distinct roots in $[c_{u},c_{u+1}]$. This till now gives us a total of $2(2^{n-2} -1)= 2^{n-1} -2$ distinct real roots.
It is now time to look at the $2^{n-2}$ type (I) intervals $[c_p, c_{p+1}]$ with $c_{p} < 0$; we once again autistically split this interval into $[c_p, e]$ and $[e, c_{p+1}]$ where $e$ is such that $p_n(e) = -2$ (as we are dealing with a type (I) case); we once again apply the intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ to gather that $g_n(x)$ contains two distinct roots in $[c_p, c_{p+1}]$. Total number roots of g_n(x) found in these type of intervals is hence $2(2^{n-2}) = 2^{n-1}$ distinct roots.
The total number of distinct roots we now have is $2^{n-1} -2 + 2^{n-1} = 2^{n-1}-2$. Where the other two roots are is a question you may ask. You will find those other two roots in the interval $[-a,a]$ where $a$ is the smallest positive root of $p_n(x)$ and you can prove yourself that this is so by doing a similar analysis to that done above.
answered Jan 20 at 12:19
acreativenameacreativename
7617
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080188%2fprove-all-roots-of-p-nx-x-are-real-and-distinct%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Hint:
Observe that $-2 le P_1(x) le 2$ for all $-2le xle 2$ and both its roots lie in the same interval. This property becomes obvious by substitution $x=2cos t$ which maps interval $tin[0,pi]$ onto $xin[-2,2]$.
We have:
$$
P_1(2cos t)=(2cos t)^2-2=4frac{1+cos 2t}{2}-2=2cos 2t.
$$
Similarly by induction:
$$
P_n(2cos t)=2cos 2^n t.
$$
Thus the polynomial $P_n(x)$ has exactly $2^{n}$ roots on the interval $(-2,2)$:
$$
xi_k=2cosfrac{2k-1}{2^{n+1}}pi,quad k=1dots 2^n.
$$
Besides the polynomial has alternating $2^{n-1}+1$ maxima $P(xi_k^text{max})=2$ at
$$
xi_k^text{max}=2cosfrac{2k}{2^n}pi,quad k=0dots 2^{n-1}
$$
and $2^{n-1}$ minima $P(xi_k^text{min})=-2$ at
$$
xi_k^text{min}=2cosfrac{2k-1}{2^n}pi,quad k=1dots 2^{n-1}.
$$
Note that the maxima at $x=-2$ and $x=2$ are not necessary the extreme points of the polynomial $P_n(x)$, they are just its values at the boundaries of the interval $[-2,2]$.
Note also that as the order of the polynomial $P_n(x)$ is $2^n$ we have found all the roots of the polynomial.
What remains is to prove that the function $Q(x)=x$ intersects the curve described above in exactly $2^n$ points. For this observe that on the interval $(-2,2)$ the graph of $P_n(x)$ consists of $2^n$ parts connecting adjacent maxima and minima. (Note that in fact $Q(x)$ can be any polynomial of order less than $2^n$ such that $-2<Q(x)<2$ for any $-2<x<2$.)
answered Jan 22 at 11:56
useruser
4,96611030
$endgroup$
add a comment |
$begingroup$
Hint:
Observe that $-2 le P_1(x) le 2$ for all $-2le xle 2$ and both its roots lie in the same interval. This property becomes obvious by substitution $x=2cos t$ which maps interval $tin[0,pi]$ onto $xin[-2,2]$.
We have:
$$
P_1(2cos t)=(2cos t)^2-2=4frac{1+cos 2t}{2}-2=2cos 2t.
$$
Similarly by induction:
$$
P_n(2cos t)=2cos 2^n t.
$$
Thus the polynomial $P_n(x)$ has exactly $2^{n}$ roots on the interval $(-2,2)$:
$$
xi_k=2cosfrac{2k-1}{2^{n+1}}pi,quad k=1dots 2^n.
$$
Besides the polynomial has alternating $2^{n-1}+1$ maxima $P(xi_k^text{max})=2$ at
$$
xi_k^text{max}=2cosfrac{2k}{2^n}pi,quad k=0dots 2^{n-1}
$$
and $2^{n-1}$ minima $P(xi_k^text{min})=-2$ at
$$
xi_k^text{min}=2cosfrac{2k-1}{2^n}pi,quad k=1dots 2^{n-1}.
$$
Note that the maxima at $x=-2$ and $x=2$ are not necessary the extreme points of the polynomial $P_n(x)$, they are just its values at the boundaries of the interval $[-2,2]$.
Note also that as the order of the polynomial $P_n(x)$ is $2^n$ we have found all the roots of the polynomial.
What remains is to prove that the function $Q(x)=x$ intersects the curve described above in exactly $2^n$ points. For this observe that on the interval $(-2,2)$ the graph of $P_n(x)$ consists of $2^n$ parts connecting adjacent maxima and minima. (Note that in fact $Q(x)$ can be any polynomial of order less than $2^n$ such that $-2<Q(x)<2$ for any $-2<x<2$.)
answered Jan 22 at 11:56
useruser
4,96611030
$endgroup$
add a comment |
$begingroup$
Hint:
Observe that $-2 le P_1(x) le 2$ for all $-2le xle 2$ and both its roots lie in the same interval. This property becomes obvious by substitution $x=2cos t$ which maps interval $tin[0,pi]$ onto $xin[-2,2]$.
We have:
$$
P_1(2cos t)=(2cos t)^2-2=4frac{1+cos 2t}{2}-2=2cos 2t.
$$
Similarly by induction:
$$
P_n(2cos t)=2cos 2^n t.
$$
Thus the polynomial $P_n(x)$ has exactly $2^{n}$ roots on the interval $(-2,2)$:
$$
xi_k=2cosfrac{2k-1}{2^{n+1}}pi,quad k=1dots 2^n.
$$
Besides the polynomial has alternating $2^{n-1}+1$ maxima $P(xi_k^text{max})=2$ at
$$
xi_k^text{max}=2cosfrac{2k}{2^n}pi,quad k=0dots 2^{n-1}
$$
and $2^{n-1}$ minima $P(xi_k^text{min})=-2$ at
$$
xi_k^text{min}=2cosfrac{2k-1}{2^n}pi,quad k=1dots 2^{n-1}.
$$
Note that the maxima at $x=-2$ and $x=2$ are not necessary the extreme points of the polynomial $P_n(x)$, they are just its values at the boundaries of the interval $[-2,2]$.
Note also that as the order of the polynomial $P_n(x)$ is $2^n$ we have found all the roots of the polynomial.
What remains is to prove that the function $Q(x)=x$ intersects the curve described above in exactly $2^n$ points. For this observe that on the interval $(-2,2)$ the graph of $P_n(x)$ consists of $2^n$ parts connecting adjacent maxima and minima. (Note that in fact $Q(x)$ can be any polynomial of order less than $2^n$ such that $-2<Q(x)<2$ for any $-2<x<2$.)
answered Jan 22 at 11:56
useruser
4,96611030
$endgroup$
Hint:
Observe that $-2 le P_1(x) le 2$ for all $-2le xle 2$ and both its roots lie in the same interval. This property becomes obvious by substitution $x=2cos t$ which maps interval $tin[0,pi]$ onto $xin[-2,2]$.
We have:
$$
P_1(2cos t)=(2cos t)^2-2=4frac{1+cos 2t}{2}-2=2cos 2t.
$$
Similarly by induction:
$$
P_n(2cos t)=2cos 2^n t.
$$
Thus the polynomial $P_n(x)$ has exactly $2^{n}$ roots on the interval $(-2,2)$:
$$
xi_k=2cosfrac{2k-1}{2^{n+1}}pi,quad k=1dots 2^n.
$$
Besides the polynomial has alternating $2^{n-1}+1$ maxima $P(xi_k^text{max})=2$ at
$$
xi_k^text{max}=2cosfrac{2k}{2^n}pi,quad k=0dots 2^{n-1}
$$
and $2^{n-1}$ minima $P(xi_k^text{min})=-2$ at
$$
xi_k^text{min}=2cosfrac{2k-1}{2^n}pi,quad k=1dots 2^{n-1}.
$$
Note that the maxima at $x=-2$ and $x=2$ are not necessary the extreme points of the polynomial $P_n(x)$, they are just its values at the boundaries of the interval $[-2,2]$.
Note also that as the order of the polynomial $P_n(x)$ is $2^n$ we have found all the roots of the polynomial.
What remains is to prove that the function $Q(x)=x$ intersects the curve described above in exactly $2^n$ points. For this observe that on the interval $(-2,2)$ the graph of $P_n(x)$ consists of $2^n$ parts connecting adjacent maxima and minima. (Note that in fact $Q(x)$ can be any polynomial of order less than $2^n$ such that $-2<Q(x)<2$ for any $-2<x<2$.)
answered Jan 22 at 11:56
useruser
4,96611030
edited Jan 22 at 19:34
answered Jan 22 at 11:56
useruser
4,96611030
answered Jan 22 at 11:56
useruser
4,96611030
answered Jan 22 at 11:56
useruser
4,96611030
4,96611030
add a comment |
add a comment |
$begingroup$
Lemma; Let $n geq 2$; If $p_{n}(x)$ has a local minima it is $-2$. If $p_{n}(x)$ has a local maxima it is $2$. Local minima with $x>0$ occurs $2^{n-2}$ times, Local minima with $x<0$ occurs $2^{n-2}$ times, Local maxima with $x<0$ occurs $2^{n-2} -1$ times and finally Local maxima with $x>0$ occurs $2^{n-2}-1$ times. Local maxima occurs at $x=0$
Proof; Differentiating $p_{n}$ we find that
$p_{n}'(x) = 2p_{n-1}(x)(p_{n-1}'(x))$
Hence
(1) $p_{n}'(x) = 2p_{n-1}(x)(2p_{n-2}(x))...(2p_{1}(x))(2x)$
To be a local minima or maxima one has $p_{n}'(x) = 0$. By looking at (1) we see that some $p_{n-j}(x)$ is $0$ or $x=0$. If $p_{n-1}(x)$ is 0 then $p_{n}(x)$ is $-2$. If some $p_{n-j}(x)$ for $jgeq 2$ is $0$ (just define $p_{0}(x) = x$) then $p_{n}(x) = 2$. So if (x,p_n(x)) is a turning point p_n(x) is $pm 2$. Also note that there are no double roots as if $p_h(x) = 0$ then for any $a >0$ $p_{h+a}(x) = 2$ or $-2$
Now note that each $p_n(x)$ has $2^{n}$ distinct roots. So we can label the roots in an increasing order $c_{1} < c_{2} ...< c_{2^n}$. Observe that between any two successive roots $c_{u}$ and $c_{u+1}$ one has a turning point.
We claim that between any successive roots there is exactly one turning point. To see this suppose that there is an interval $[c_u,c_{u+1}]$ that contains atleast two turning points; hence there are at least $2^n$ turning points in $[c_{1},c_{2^n}]$ but there can only be at most $2^n-1$ turning points (as degree of $p_n(x)$ is $2^{n}$). Combining this information and the information in the previous paragraph we have that in an interval $[c_{u}, c_{u+1}]$
; $p_n(x)$ attains exactly one of the following;
(I) A local minima of -2
(II) A local maxima of 2
Going all the way back and looking at (1) (the equation above) (I) occurs exactly when $p_{n-1}(x) = 0$ which has $2^{n-1}$ distinct roots; half positive and half negative (even function). (II) occurs exactly when some $p_{n-j}(x) =0$ for some $j geq 2$ which happens at $2^{n-1} - 1$ distinct places with one of them being $0$.
We will use the observation that the roots of $p_n(x)$ satisfy $|x| < 2$ to finish the proof.
Now consider each of the $2^{n-2} -1$ type (II) intervals $[c_{u},c_{u+1}]$ with $c_{u} > 0$ we can split this interval into two intervals $[c_{u},d]$ and $[d,c_{u+1}]$ where $p_n(d) = 2$ applying intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ we find that $g_n(x)$ contains two distinct roots in $[c_{u},c_{u+1}]$. This till now gives us a total of $2(2^{n-2} -1)= 2^{n-1} -2$ distinct real roots.
It is now time to look at the $2^{n-2}$ type (I) intervals $[c_p, c_{p+1}]$ with $c_{p} < 0$; we once again autistically split this interval into $[c_p, e]$ and $[e, c_{p+1}]$ where $e$ is such that $p_n(e) = -2$ (as we are dealing with a type (I) case); we once again apply the intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ to gather that $g_n(x)$ contains two distinct roots in $[c_p, c_{p+1}]$. Total number roots of g_n(x) found in these type of intervals is hence $2(2^{n-2}) = 2^{n-1}$ distinct roots.
The total number of distinct roots we now have is $2^{n-1} -2 + 2^{n-1} = 2^{n-1}-2$. Where the other two roots are is a question you may ask. You will find those other two roots in the interval $[-a,a]$ where $a$ is the smallest positive root of $p_n(x)$ and you can prove yourself that this is so by doing a similar analysis to that done above.
answered Jan 20 at 12:19
acreativenameacreativename
7617
$endgroup$
add a comment |
$begingroup$
Lemma; Let $n geq 2$; If $p_{n}(x)$ has a local minima it is $-2$. If $p_{n}(x)$ has a local maxima it is $2$. Local minima with $x>0$ occurs $2^{n-2}$ times, Local minima with $x<0$ occurs $2^{n-2}$ times, Local maxima with $x<0$ occurs $2^{n-2} -1$ times and finally Local maxima with $x>0$ occurs $2^{n-2}-1$ times. Local maxima occurs at $x=0$
Proof; Differentiating $p_{n}$ we find that
$p_{n}'(x) = 2p_{n-1}(x)(p_{n-1}'(x))$
Hence
(1) $p_{n}'(x) = 2p_{n-1}(x)(2p_{n-2}(x))...(2p_{1}(x))(2x)$
To be a local minima or maxima one has $p_{n}'(x) = 0$. By looking at (1) we see that some $p_{n-j}(x)$ is $0$ or $x=0$. If $p_{n-1}(x)$ is 0 then $p_{n}(x)$ is $-2$. If some $p_{n-j}(x)$ for $jgeq 2$ is $0$ (just define $p_{0}(x) = x$) then $p_{n}(x) = 2$. So if (x,p_n(x)) is a turning point p_n(x) is $pm 2$. Also note that there are no double roots as if $p_h(x) = 0$ then for any $a >0$ $p_{h+a}(x) = 2$ or $-2$
Now note that each $p_n(x)$ has $2^{n}$ distinct roots. So we can label the roots in an increasing order $c_{1} < c_{2} ...< c_{2^n}$. Observe that between any two successive roots $c_{u}$ and $c_{u+1}$ one has a turning point.
We claim that between any successive roots there is exactly one turning point. To see this suppose that there is an interval $[c_u,c_{u+1}]$ that contains atleast two turning points; hence there are at least $2^n$ turning points in $[c_{1},c_{2^n}]$ but there can only be at most $2^n-1$ turning points (as degree of $p_n(x)$ is $2^{n}$). Combining this information and the information in the previous paragraph we have that in an interval $[c_{u}, c_{u+1}]$
; $p_n(x)$ attains exactly one of the following;
(I) A local minima of -2
(II) A local maxima of 2
Going all the way back and looking at (1) (the equation above) (I) occurs exactly when $p_{n-1}(x) = 0$ which has $2^{n-1}$ distinct roots; half positive and half negative (even function). (II) occurs exactly when some $p_{n-j}(x) =0$ for some $j geq 2$ which happens at $2^{n-1} - 1$ distinct places with one of them being $0$.
We will use the observation that the roots of $p_n(x)$ satisfy $|x| < 2$ to finish the proof.
Now consider each of the $2^{n-2} -1$ type (II) intervals $[c_{u},c_{u+1}]$ with $c_{u} > 0$ we can split this interval into two intervals $[c_{u},d]$ and $[d,c_{u+1}]$ where $p_n(d) = 2$ applying intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ we find that $g_n(x)$ contains two distinct roots in $[c_{u},c_{u+1}]$. This till now gives us a total of $2(2^{n-2} -1)= 2^{n-1} -2$ distinct real roots.
It is now time to look at the $2^{n-2}$ type (I) intervals $[c_p, c_{p+1}]$ with $c_{p} < 0$; we once again autistically split this interval into $[c_p, e]$ and $[e, c_{p+1}]$ where $e$ is such that $p_n(e) = -2$ (as we are dealing with a type (I) case); we once again apply the intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ to gather that $g_n(x)$ contains two distinct roots in $[c_p, c_{p+1}]$. Total number roots of g_n(x) found in these type of intervals is hence $2(2^{n-2}) = 2^{n-1}$ distinct roots.
The total number of distinct roots we now have is $2^{n-1} -2 + 2^{n-1} = 2^{n-1}-2$. Where the other two roots are is a question you may ask. You will find those other two roots in the interval $[-a,a]$ where $a$ is the smallest positive root of $p_n(x)$ and you can prove yourself that this is so by doing a similar analysis to that done above.
answered Jan 20 at 12:19
acreativenameacreativename
7617
$endgroup$
add a comment |
$begingroup$
Lemma; Let $n geq 2$; If $p_{n}(x)$ has a local minima it is $-2$. If $p_{n}(x)$ has a local maxima it is $2$. Local minima with $x>0$ occurs $2^{n-2}$ times, Local minima with $x<0$ occurs $2^{n-2}$ times, Local maxima with $x<0$ occurs $2^{n-2} -1$ times and finally Local maxima with $x>0$ occurs $2^{n-2}-1$ times. Local maxima occurs at $x=0$
Proof; Differentiating $p_{n}$ we find that
$p_{n}'(x) = 2p_{n-1}(x)(p_{n-1}'(x))$
Hence
(1) $p_{n}'(x) = 2p_{n-1}(x)(2p_{n-2}(x))...(2p_{1}(x))(2x)$
To be a local minima or maxima one has $p_{n}'(x) = 0$. By looking at (1) we see that some $p_{n-j}(x)$ is $0$ or $x=0$. If $p_{n-1}(x)$ is 0 then $p_{n}(x)$ is $-2$. If some $p_{n-j}(x)$ for $jgeq 2$ is $0$ (just define $p_{0}(x) = x$) then $p_{n}(x) = 2$. So if (x,p_n(x)) is a turning point p_n(x) is $pm 2$. Also note that there are no double roots as if $p_h(x) = 0$ then for any $a >0$ $p_{h+a}(x) = 2$ or $-2$
Now note that each $p_n(x)$ has $2^{n}$ distinct roots. So we can label the roots in an increasing order $c_{1} < c_{2} ...< c_{2^n}$. Observe that between any two successive roots $c_{u}$ and $c_{u+1}$ one has a turning point.
We claim that between any successive roots there is exactly one turning point. To see this suppose that there is an interval $[c_u,c_{u+1}]$ that contains atleast two turning points; hence there are at least $2^n$ turning points in $[c_{1},c_{2^n}]$ but there can only be at most $2^n-1$ turning points (as degree of $p_n(x)$ is $2^{n}$). Combining this information and the information in the previous paragraph we have that in an interval $[c_{u}, c_{u+1}]$
; $p_n(x)$ attains exactly one of the following;
(I) A local minima of -2
(II) A local maxima of 2
Going all the way back and looking at (1) (the equation above) (I) occurs exactly when $p_{n-1}(x) = 0$ which has $2^{n-1}$ distinct roots; half positive and half negative (even function). (II) occurs exactly when some $p_{n-j}(x) =0$ for some $j geq 2$ which happens at $2^{n-1} - 1$ distinct places with one of them being $0$.
We will use the observation that the roots of $p_n(x)$ satisfy $|x| < 2$ to finish the proof.
Now consider each of the $2^{n-2} -1$ type (II) intervals $[c_{u},c_{u+1}]$ with $c_{u} > 0$ we can split this interval into two intervals $[c_{u},d]$ and $[d,c_{u+1}]$ where $p_n(d) = 2$ applying intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ we find that $g_n(x)$ contains two distinct roots in $[c_{u},c_{u+1}]$. This till now gives us a total of $2(2^{n-2} -1)= 2^{n-1} -2$ distinct real roots.
It is now time to look at the $2^{n-2}$ type (I) intervals $[c_p, c_{p+1}]$ with $c_{p} < 0$; we once again autistically split this interval into $[c_p, e]$ and $[e, c_{p+1}]$ where $e$ is such that $p_n(e) = -2$ (as we are dealing with a type (I) case); we once again apply the intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ to gather that $g_n(x)$ contains two distinct roots in $[c_p, c_{p+1}]$. Total number roots of g_n(x) found in these type of intervals is hence $2(2^{n-2}) = 2^{n-1}$ distinct roots.
The total number of distinct roots we now have is $2^{n-1} -2 + 2^{n-1} = 2^{n-1}-2$. Where the other two roots are is a question you may ask. You will find those other two roots in the interval $[-a,a]$ where $a$ is the smallest positive root of $p_n(x)$ and you can prove yourself that this is so by doing a similar analysis to that done above.
answered Jan 20 at 12:19
acreativenameacreativename
7617
$endgroup$
Lemma; Let $n geq 2$; If $p_{n}(x)$ has a local minima it is $-2$. If $p_{n}(x)$ has a local maxima it is $2$. Local minima with $x>0$ occurs $2^{n-2}$ times, Local minima with $x<0$ occurs $2^{n-2}$ times, Local maxima with $x<0$ occurs $2^{n-2} -1$ times and finally Local maxima with $x>0$ occurs $2^{n-2}-1$ times. Local maxima occurs at $x=0$
Proof; Differentiating $p_{n}$ we find that
$p_{n}'(x) = 2p_{n-1}(x)(p_{n-1}'(x))$
Hence
(1) $p_{n}'(x) = 2p_{n-1}(x)(2p_{n-2}(x))...(2p_{1}(x))(2x)$
To be a local minima or maxima one has $p_{n}'(x) = 0$. By looking at (1) we see that some $p_{n-j}(x)$ is $0$ or $x=0$. If $p_{n-1}(x)$ is 0 then $p_{n}(x)$ is $-2$. If some $p_{n-j}(x)$ for $jgeq 2$ is $0$ (just define $p_{0}(x) = x$) then $p_{n}(x) = 2$. So if (x,p_n(x)) is a turning point p_n(x) is $pm 2$. Also note that there are no double roots as if $p_h(x) = 0$ then for any $a >0$ $p_{h+a}(x) = 2$ or $-2$
Now note that each $p_n(x)$ has $2^{n}$ distinct roots. So we can label the roots in an increasing order $c_{1} < c_{2} ...< c_{2^n}$. Observe that between any two successive roots $c_{u}$ and $c_{u+1}$ one has a turning point.
We claim that between any successive roots there is exactly one turning point. To see this suppose that there is an interval $[c_u,c_{u+1}]$ that contains atleast two turning points; hence there are at least $2^n$ turning points in $[c_{1},c_{2^n}]$ but there can only be at most $2^n-1$ turning points (as degree of $p_n(x)$ is $2^{n}$). Combining this information and the information in the previous paragraph we have that in an interval $[c_{u}, c_{u+1}]$
; $p_n(x)$ attains exactly one of the following;
(I) A local minima of -2
(II) A local maxima of 2
Going all the way back and looking at (1) (the equation above) (I) occurs exactly when $p_{n-1}(x) = 0$ which has $2^{n-1}$ distinct roots; half positive and half negative (even function). (II) occurs exactly when some $p_{n-j}(x) =0$ for some $j geq 2$ which happens at $2^{n-1} - 1$ distinct places with one of them being $0$.
We will use the observation that the roots of $p_n(x)$ satisfy $|x| < 2$ to finish the proof.
Now consider each of the $2^{n-2} -1$ type (II) intervals $[c_{u},c_{u+1}]$ with $c_{u} > 0$ we can split this interval into two intervals $[c_{u},d]$ and $[d,c_{u+1}]$ where $p_n(d) = 2$ applying intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ we find that $g_n(x)$ contains two distinct roots in $[c_{u},c_{u+1}]$. This till now gives us a total of $2(2^{n-2} -1)= 2^{n-1} -2$ distinct real roots.
It is now time to look at the $2^{n-2}$ type (I) intervals $[c_p, c_{p+1}]$ with $c_{p} < 0$; we once again autistically split this interval into $[c_p, e]$ and $[e, c_{p+1}]$ where $e$ is such that $p_n(e) = -2$ (as we are dealing with a type (I) case); we once again apply the intermediate value theorem in each of the intervals to the function $g_n(x) = p_n(x) - x$ to gather that $g_n(x)$ contains two distinct roots in $[c_p, c_{p+1}]$. Total number roots of g_n(x) found in these type of intervals is hence $2(2^{n-2}) = 2^{n-1}$ distinct roots.
The total number of distinct roots we now have is $2^{n-1} -2 + 2^{n-1} = 2^{n-1}-2$. Where the other two roots are is a question you may ask. You will find those other two roots in the interval $[-a,a]$ where $a$ is the smallest positive root of $p_n(x)$ and you can prove yourself that this is so by doing a similar analysis to that done above.
answered Jan 20 at 12:19
acreativenameacreativename
7617
answered Jan 20 at 12:19
acreativenameacreativename
7617
answered Jan 20 at 12:19
acreativenameacreativename
7617
answered Jan 20 at 12:19
acreativenameacreativename
7617
7617
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3080188%2fprove-all-roots-of-p-nx-x-are-real-and-distinct%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
The relationship between the roots of the successive polynomials is clearer if you write $p_k(x)=p_{k-1}(p_1(x))$ instead.
$endgroup$
– Eric Wofsey
Jan 20 at 5:18