5

Let $P(x)=x^2 +2013x+1$. Show that $P(P(\cdots P(x))\cdots)=0$ (i.e. $P$ is $n$-times nested) has at least one real root for any $n$ $P$.

For $n = 1$ this is obvious. Next, for $n = 2$ we get a fourth order polynomial $$x^4 + 4,026 x^3 + 4,054,184 x + 2,015$$ and by substituiting $y = x + 2,013/2$ can elimate the cubic term. Rearranging and standardizing yields a 4th order equation $$y^4 – 4,048,139/2 y^2 + 16,387,413,154,661/16 = 0$$ It can be solved but further substitutions quickly become intractable and don´t lead anywhere. Can anyone help? Thanks.

Parzifal
  • 189

2 Answers2

3

Let $P_{1}(x) = P(x)$

Let $P_{n}(x) = P(P_{n-1}(x))$

Let $x_{n}$ be one of the solution for $P_{n}(x) = 0$

Initiation

Both roots of $P(x)$ are real and negative.

We choose the less negative solution $x_{1}$.

$x_{1} = \frac{-2013 + \sqrt{2013^{2} - 4(1 - 0)}}{2}$.

Notice that $0 \ge x_{1} \ge -2013/2$.

Induction

From the last step of the induction, we have $0 \ge x_{n-1} \ge -2013/2$.

One of the solution of $P_{n}(x) = 0$ is the solution of:

$P(x) = x_{n-1}$

Again, we can choose a real and negative solution $x_{n}$ such that $0 \ge x_{n} \ge -2013/2$:

$x_{n} = \frac{-2013 + \sqrt{2013^{2} - 4(1 - x_{n-1})}}{2}$

R zu
  • 697
  • 3
  • 17
  • Both roots of $P(x)$ are real and negative. Are you picking a specific one of them, or doesn't it matter? – Arthur Oct 27 '18 at 20:43
  • Can you explain the notation $x_n$ and $x_{n - 1}?$ – green frog Oct 27 '18 at 20:45
  • @R zu: Thank you very much. It seems a clever approach to use iteration. But could you please explain your thoughts a bit more for a novice like me, in particular your conclusion? Much appreciated. – Parzifal Oct 27 '18 at 20:55
  • should be correct and clear now. – R zu Oct 27 '18 at 21:16
  • @Arthur: Choosing a more negative solution in all steps also works. I haven't thought about whether all possible choices in all step would work. – R zu Oct 27 '18 at 21:31
  • @R zu: Key to your solution is the fact that x(n) + 2013x(n) + 1= x(n-1). From the explicit solutions of the first two steps this becomes clear to me. But could you give me a more intuitive explanation? You immediately seem to have recognized this when you solved the problem. Thanks. – Parzifal Oct 28 '18 at 07:41
  • I see this as a full binary tree. Each iteration (or nesting of P) makes the number of solution doubles (if we treat two solutions with same value as different branches). I choose a path from the root to the leaf that would reach a real solution. http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html – R zu Oct 28 '18 at 13:42
  • @R zu: Could you please explain how (and why) the iteration formula x(n-1) = x(n)^2 + 2013x(n) + 1 follows from the nesting of p? Would very much appreciate some guidance. Thanks – Parzifal Oct 30 '18 at 06:37
  • $P(P(x)) = 0$ implies $P(y) = 0$ where $y = P(x)$. That means the following: Firstly, $P(y) = 0$, which means $y^{2} + 2013y + 1 = 0$. Secondly, $y = P(x)$, which means $P(x) - y = 0$ and $x^{2} + 2013x + 1 - y = 0$ – R zu Nov 03 '18 at 02:54
  • I try to peel the outermost $P(...)$ from the nested function. Informally, $P(P(P(x))) = 0$ implies $P(P(x)) = P^{-1}(0)$ and $y = P^{-1}(0)$ is the solution of $P(y) = 0$. Notice that using inverse here is not correct because the inverse function may not exist if $P$ is not a one to one map. – R zu Nov 03 '18 at 03:10
3

R zu's is a nice algebraic answer. Here is a more geometric way of seeing it. Let $$P(x) = x^2 + bx + 1$$ where $b$ is any real number. $P(x)$ tends to $\infty$ as $x$ tends to $+\infty$ or $-\infty$ and achieves its minimum where $P'(x) = 2x + b = 0$, i.e., at $x = -b/2$. The value of that minimum is $P(-b/2) = 1 - b^2/4$. So $P$ maps the interval $I = [-b/2, \infty)$ onto the interval $J = [1-b^2/4, \infty)$ (the range of the function $P$). Now assume $b$ is large enough so that $$1 - b^2/4 < -b/2 < 0$$ as is certainly the case in your example where $b = 2013$. Then $I \subseteq J$, so as $P$ maps $I$ onto $J$ and $J$ is the range of the function $P$, $P$ also maps $J$ onto $J$. Hence by induction $P_n$ (defined by $P_1(x) = P(x)$ and $P_n(x) = P(P_{n-1}(x))$ as in R zu's answer) maps $J$ onto $J$ and as $0 \in J$, this means $P_n$ has a root.

Just for fun, here's a plot of $P_1$, $P_2$ and $P_3$ for $b = 4$, illustrating that the the range of each of these functions is $J = [-3, \infty)$.

enter image description here

Rob Arthan
  • 48,577
  • 1
    Is this related to something about dynamical systems? What branches of mathematics study this? – R zu Oct 28 '18 at 13:58
  • I don't know much about dynamical systems and ergodic theory, I'm afraid. I was just thinking about the shape of the graph and what subintervals of the domain map onto the range. Maybe someone else can comment on branches of mathematics that study generalisation of this kind of thing. – Rob Arthan Oct 28 '18 at 14:11
  • This is a very interesting depiction – Parzifal Oct 28 '18 at 17:12
  • @Parzifal: indeed! One interesting question it raises is "are the local maxima of $P_n(x)$ for $n > 1$ all equal to $-2$?". – Rob Arthan Oct 28 '18 at 18:58