# Nested functions

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.

• Can you share some context? Why is this problem interesting for you? Why 17, for example? Aug 12, 2020 at 14:56
• The sequence grows very slowly. It reaches about $3.23$ after 10000 steps. Aug 12, 2020 at 15:47
• Mathematica or Wolfram Alpha: f[n_]:=Nest[L, N[17/n], n] n (I'm not sure about how accurate it is, but it seems stable enough.) Aug 12, 2020 at 15:53
• Can't do that unfortunately. Just take large $n$, but the larger, the longer it takes to work it out. It might not be accurate because it's nested a large number of times and using an approximation for $17/n$. Aug 12, 2020 at 16:48
• That seems to be related with the logistic map and chaos. Take a look: en.wikipedia.org/wiki/Logistic_map. Aug 12, 2020 at 17:23

## 2 Answers

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.

• Then we (seem to) have $f(x) = \frac{2x}{2+x} \to 2$. But the experiments say that $f(x) \to 4$. For a general $x$, what we need to change on the proof? Aug 12, 2020 at 19:43
• I'm not quite sure what you mean by $f(x)$ here. Aug 12, 2020 at 19:46
• in the statement of the problem you've written $L(x) = x - x^2/4$ (rather than $x - x^2/2$), which should then give an answer of $\lim na_n = \frac{4 \cdot 17}{4 + 17} = \frac{68}{21}$, right? Aug 12, 2020 at 19:46
• That's it! Experimentally we also get $\frac{68}{21}$. Aug 12, 2020 at 19:48

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.

• This is an interesting find. So if only extremal coefficients matter, than I would be inclined to spend my time with higher values of $n$ rather than focus on the smaller ones. I appreciate this. Aug 12, 2020 at 19:06
• I also reinforce that the logistic map is quite similar to this map and it is well studied. We can write $L(4x) = 4x(x-1)$ and that is the logistic map with $r=4$, one of the few cases where the logistic map is deterministic at the limit. Aug 12, 2020 at 19:18