# Defining recursive non-linear recurrence relation

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.

No need to define eps0:

Clear[eps]
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]]


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)];

Manipulate[
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.

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

ClearAll[eps];
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.