Nested functions

Question

Assuming that we have some function $L(x)$ such that $L(x) = x - \frac{x^2}{4}.$ Now, define $a_n$ as $$L \Bigl( L \Bigl( L \Bigl( \cdots L \Bigl( \frac{17}{n} \Bigr) \cdots \Bigr) \Bigr) \Bigr),$$ where we have $n$ iterations of $L.$ My question here is, what value does $n \cdot a_n$ approach as $n$ approaches infinity?

I tried to find some sort of pattern but it got nasty fast. I than tried to find a few small values and test them out, but they didn't quite work. How should I approach this problem? Thanks.

Answer 1

I'd like to post the solution I came up with.

Note that $0 < L(x) < x$ for $0 < x < 2.$ Assuming $n$ is sufficiently large, i.e. $n \ge 9,$ we have that $0 < a_n < \frac{17}{n} < 2.$

From $L(x) = x - \frac{x^2}{2},$ we can write $$\frac{1}{L(x)} = \frac{1}{x - \frac{x^2}{2}} = \frac{2}{2x - x^2} = \frac{2}{x(2 - x)} = \frac{x + (2 - x)}{x(2 - x)} = \frac{1}{x} + \frac{1}{2 - x},$$ so $$\frac{1}{L(x)} - \frac{1}{x} = \frac{1}{2 - x} \quad (*).$$ For a nonnegative integer $k,$ let $L^{(k)}(x)$ denote the $k$th iterate of $L(x).$ Then $0 < L^{(k)}(x) < x,$ so $$0 < L^{(k)} \left( \frac{17}{n} \right) \le \frac{17}{n}.$$ Hence, $$\frac{1}{2} < \frac{1}{2 - L^{(k)} (\frac{17}{n})} \le \frac{1}{2 - \frac{17}{n}} = \frac{n}{2n - 17}.$$ By equation $(*),$ $$\frac{1}{L^{(k + 1)} (\frac{17}{n})} - \frac{1}{L^{(k)} (\frac{17}{n})} = \frac{1}{2 - L^{(k)} (\frac{17}{n})},$$ so $$\frac{1}{2} < \frac{1}{L^{(k + 1)} (\frac{17}{n})} - \frac{1}{L^{(k)} (\frac{17}{n})} \le \frac{n}{2n - 17}.$$ Summing over $0 \le k \le n - 1,$ we get $$\frac{n}{2} < \frac{1}{L^{(n)} (\frac{17}{n})} - \frac{1}{\frac{17}{n}} \le \frac{n^2}{2n - 17}.$$ Since $a_n = L^{(n)} \left( \frac{17}{n} \right),$ this becomes $$\frac{n}{2} < \frac{1}{a_n} - \frac{n}{17} \le \frac{n^2}{2n - 17}.$$ Dividing by $n,$ we get $$\frac{1}{2} < \frac{1}{na_n} - \frac{1}{17} \le \frac{n}{2n - 17}.$$ As $n$ approaches infinity, $\frac{n}{2n - 17}$ approaches $\frac{1}{2},$ so if $L$ is the limit of $na_n,$ then $$\frac{1}{L} - \frac{1}{17} = \frac{1}{2}.$$ Solving, we find $L = \boxed{\frac{34}{19}}.$

Thanks to the people who helped me with this problem.

Answer 2

This is not a full answer, just a comment. I apologize to post it as an answer, but I wanted to upload an image.

First, a plot of $f(x) = \lim_{n\to\infty} na_n(x)$ (your case is $x=17$), obtained using $n=10000$ (at this point it seems to be close enough to the limit):

I tried to fit some obvious curves like $f(x) = \log(\alpha x+\beta)$ or $f(x) = \alpha x^{\frac{1}{3}}$, etc. All failed. So, I tried to see the big picture:

And by some reason it seems that $\lim_{x\to\infty} f(x) = 4$. This solves nothing, but poses another question: why, god, why?

And second, it is not difficult to find a closed formula to $L^{(n)}(x)$. By induction we can show that $$ L^{(n)}(x) = \sum_{k=1}^{2^n} a_{n,k} x^k $$ for some $a_{n,k}$.

The case $n=1$ has $a_{1,1} = 1$ and $a_{1,2} = -\frac{1}{4}$. Now assume it is true for $n\geq 1$. We have: $$ \begin{align} L^{(n+1)}(x) &= \sum_{k=1}^{2^{n}} a_{n,k} \left(x - \frac{1}{4}x^2\right)^k\\ &= \sum_{k=1}^{2^{n}} a_{n,k} \sum_{j=0}^k { k \choose j } \left( - \frac{1}{4} \right)^{j} x^{k+j}\\ &= \sum_{k=1}^{2^{n+1}} a_{n+1,k} x^k\\ \end{align} $$

with $$ a_{n+1, k} = \sum_{\substack{0\leq i\leq j\\ i+j=k}} a_{n,j} { j \choose i} \left( - \frac{1}{4} \right)^{i} = \sum_{\substack{0\leq i\leq \left[\frac{k}{2}\right]}} a_{n,k-i} { k-i \choose i} \left( - \frac{1}{4} \right)^{i}. $$

Using Stirling we know that $${ j \choose i } \sim \frac{1}{\sqrt{2\pi j}}\left(\frac{je}{i} \right)^i$$ and so, $$ a_{n+1, k} \sim \sum_{\substack{0\leq i\leq \left[\frac{k}{2}\right]}} a_{n,k-i} \frac{1}{\sqrt{2\pi (k-i)}}\left(- \frac{e(k-i)}{4i} \right)^i. $$

That approximation suggests that the only the extremal coefficients (with high or low values of $k$) are meaningful. But I can't go further.