8
$\begingroup$

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.

$\endgroup$
10
  • 6
    $\begingroup$ Can you share some context? Why is this problem interesting for you? Why 17, for example? $\endgroup$ Aug 12, 2020 at 14:56
  • 2
    $\begingroup$ The sequence grows very slowly. It reaches about $3.23$ after 10000 steps. $\endgroup$ Aug 12, 2020 at 15:47
  • 2
    $\begingroup$ 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.) $\endgroup$ Aug 12, 2020 at 15:53
  • 2
    $\begingroup$ 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$. $\endgroup$ Aug 12, 2020 at 16:48
  • 1
    $\begingroup$ That seems to be related with the logistic map and chaos. Take a look: en.wikipedia.org/wiki/Logistic_map. $\endgroup$ Aug 12, 2020 at 17:23

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Aug 12, 2020 at 19:43
  • $\begingroup$ I'm not quite sure what you mean by $f(x)$ here. $\endgroup$ Aug 12, 2020 at 19:46
  • 1
    $\begingroup$ 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? $\endgroup$
    – user125932
    Aug 12, 2020 at 19:46
  • $\begingroup$ That's it! Experimentally we also get $\frac{68}{21}$. $\endgroup$ Aug 12, 2020 at 19:48
2
$\begingroup$

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):

enter image description here

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:

enter image description here

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 12, 2020 at 19:06
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 12, 2020 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.