I have a non-linear recurrence relation:

$$\epsilon_i = \sqrt{\frac{2}{1+\epsilon_{i-1}}}\epsilon_{i-1}$$ Here, $\epsilon_0\in[0,1]$, but it's really some function $f(n,p)$ for some other parameters.

I've derived by hand a lower bound $\ell_i$, and upper bound $u_i$ for $\epsilon_i$. These are all functions of $i$ (and implicitly $\epsilon_0$), and I know that:

$$\ell_i \leq \epsilon_i\leq u_i,\quad \forall i$$

I want to use mathematica to "explore" how tight these bounds are somewhat. Ideally, I'd:

  1. Plot all three bounds (for say $i\in[1, 1000]$)
  2. Put this in a manipulate call, so manipulate $n, p$.

I've worked out how to do this without the recurrence relation (so for solely the bounds). My code for the recurrence relation seems to have issues though:

eps0[n_, p_] := Sqrt[(p * Log[2] + Log[p])/(2 n)]
eps[i_, n_, p_] := (Sqrt[2] * eps[i - 1, n, p])/Sqrt[1 + eps[i - 1, n, p]]
eps[0, n_, p_] := eps0[n, p]

This unfortunately causes a recursion depth error, even though it seems like I defined the base case $\epsilon[0, n, p] = \epsilon_0[n, p]$, like I was supposed to.


3 Answers 3


No need to define eps0:

eps[0, n_, p_] := Sqrt[(p*Log[2] + Log[p])/(2 n)]
eps[i_, n_, p_] := (Sqrt[2]*eps[i - 1, n, p])/Sqrt[1 + eps[i - 1, n, p]]

enter image description here

You may want to introduce memoization, and/or to force eps to evaluate on numeric inputs only. I leave this to you, but feel free to ask for more details if you need to.


Not sure why you are running this backwards. Maybe use FixedPointList[ ] and start from $\epsilon_{0}$? This code works.

eps0[n_, p_] := Sqrt[(p*Log[2] + Log[p])/(2 n)];

         ListPlot@FixedPointList[# Sqrt[2./(1 + #)] &, eps0[n, p], 1000], 
         {n, 1, 100, 1}, 
         {p, 1, 10}

I don't know what the bounds are on your parameters. For the bounds I set, the plot updates as fast as you move the sliders. The fixed point is limited to 1000 iterations, but seems to always stop at about 130.

enter image description here


The problem seems to be that you have not used memoization. Use

eps0[n_, p_] := Sqrt[(p*Log[2] + Log[p])/(2 n)];
eps[i_, n_, p_] := eps[i, n, p] = 
     (Sqrt[2]*eps[i - 1, n, p])/Sqrt[1 + eps[i - 1, n, p]];
eps[0, n_, p_] := eps0[n, p];

Then you can explore the recursion with something like

DiscretePlot[eps[n, .5, 1.1], {n, 300}]

It is important to use ClearAll[eps] because the memoization will save function values, and if you ever change the definition of eps[] then the saved values will probably be wrong.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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