4

I am simply curious if starting with $f(x)=x^2+x+1$ you can compute $f(...f(f(x)))$ where $f$ appears $n$ times. I think this can be done by induction, but I tried computing $f(f(x))$, $f(f(f(x))$ and they don't look alike so I could't establish the induction hypothesis. Please help! Thank you!

This kind of exercise is pretty easy when $g(x)=ax+b$ since you can set the induction easily. But I am in the position of needing to find the roots of the polynomial $f(f(...f((x)))+constant$ and it drives me crazy since I have no ideas.

furfur
  • 598
  • This paper may be helpful. The existence of that paper indicates that maybe it does not have a nice closed form. – Kemono Chen Apr 28 '20 at 08:21
  • @furfur I have added, right at the end, an explanation showing that this is operational for finding all the roots under the form $a_0\pm \sqrt{a_1 \pm \sqrt{a_2\pm \cdots}}...$. – Jean Marie Apr 28 '20 at 11:46
  • By computing $f^n(x)$, do you express it as a polynomial and find its coefficients? If so, why do you want to do this? – lhf Apr 28 '20 at 11:53
  • I want to write it as a polynomial becuase I need to find the roots of the polynomials $g(x)=f^{n}(x)-\pm i$. – furfur Apr 28 '20 at 13:15
  • @furfur with the expression of the roots I give at the end, you don't need the coefficients of the polynomials. I will show it on a an example. – Jean Marie Apr 28 '20 at 14:39
  • See my Edit.... – Jean Marie Apr 28 '20 at 20:20

1 Answers1

3

Let $$f(x)=x^2+x+1=(x+\tfrac12)^2+\tfrac34 \tag{1}$$

With the following notations

$$s(x)=x^2, \ \ \ t(x)=x+\tfrac12, \ \ \ u(x)=x+\tfrac34, \ \ \ v(x)=x+\tfrac54$$

One can write (1) under a "conjugate relationship" form :

$$f=u \circ s \circ t$$

Let us examine :

$$f \circ f=(u \circ s \circ \underbrace{t) \circ (u}_v \circ s \circ t)=usvst$$

where, (convention that I will take from now on), the $\circ$ symbols are deleted for more compact formulations.

$$fff=(ff)f=(usvst)ust=u(sv)(sv)st$$

and, using once more the fact that $tu=v$ :

$$ffff=u(sv)(sv)st(ust)=u(sv)(sv)(sv)st$$

By an immediate recurrence :

$$ff\cdots f = u(vs)^{n-1}st$$

(where $ff...f(x)=f^{\circ n}(x)=f(f(...f(x)))$).

Thus,

$$f(f(...f(x)))=\left(...\left(\left(\left((x+\tfrac12)^2+\tfrac52\right)^2+\tfrac52\right)^2+\tfrac52\right)^2 \cdots +\tfrac52\right)^2+\tfrac34$$

making rather easy to find the $2^n$ roots of an equation of the form

$$f(f(...f(x)))=const. $$

by repeated extractions of square roots under the form :

$$a_0\pm \sqrt{a_1 \pm \sqrt{a_2\pm \cdots}}...$$

Remark : the paper pointed by @Kemono Chen, that I read after having written this solution, is indeed very interesting.

Edit : let us take the case of the type of equation $f(f(f(f(x))))=i$ as the one you desire to solve ; otherwise said a polynomial equation of degree 16

$$x^{16} + 8x^{15} + 40x^{14} + 140x^{13} + 390x^{12} + 884x^{11} + 1702x^{10} + 2790x^9 + 3980x^8 + 4900x^7 + 5282x^6 + 4876x^5 + 3910x^4 + 2580x^3 + 1440x^2 + 567x + 183 = i $$

Here are 8 of its 16 roots, obtained directly by using a Computer Algebra System :

$$\begin{matrix} \tfrac12 \sqrt{2\sqrt{2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ \tfrac12 \sqrt{2\sqrt{- 2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ \tfrac12 \sqrt{- 2\sqrt{2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ -\tfrac12 \sqrt{- 2\sqrt{2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ \tfrac12 \sqrt{- 2\sqrt{- 2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ -\tfrac12 \sqrt{- 2\sqrt{2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ -\tfrac12 \sqrt{2\sqrt{- 2\sqrt{-7 + 4i} - 5} - 5} - 1/2\\ -\tfrac12 \sqrt{- 2\sqrt{- 2\sqrt{-7 + 4i} - 5} - 5}- 1/2 \end{matrix}$$

(of course it is square roots in the complex sense).

Do you see the numbers $1/2$ (present as the $-1/2$ shift in the final values) and number $5/2$ hidden in these roots ?

Jean Marie
  • 81,803