I have the following non-linear recurrence:
$$y_{n+1} = \sqrt{\frac{2}{1+y_n}}y_n,\quad y_0 \in[0,1]$$
Some basic thought shows that $0$ and $1$ are fixed points of this, and that $0$ is repelling and $1$ is attracting (I am solely concerned with the region $y_i\in[0,1]$).
Non-linear recurrences rarely have closed forms in terms of elementary functions, and I doubt that this one does.
Fortunately, I don't particularly care about exact solutions, but solely close upper bounds.
Note that there's a trivial upper bound of $y_i\leq 1$, but this is insufficient for my case.
This sequence tends to converge to $1$ fairly quickly (and in the region of interest appears to be quite “regular''), so you can get a pretty good idea of what it looks like by choosing some arbitrary $y_0$ values and plotting it.
I've included python code that does this here. You should be able to type plot(1/2) to see the plot for 1/2 (for example).
Note that it continues to add lines to the plot — to remove them, delete plot.png, and reload the page (hacky I know).
For those that just want to see some pictures, see below:
Here, the lines plotted correspond to $y_0 \in\{1/2, 1/4, 1/8, 1/16, 1/32\}$, from top to bottom.
Note that this picture is slightly deceiving — this is technically a discrete sequence.
Still, this shows that it might have come reasonable continuous interpolation.
What techniques are there for getting upper bounds for monotonically-increasing non-linear recurrence relations?
The only thought I have is approximating $y_n\sqrt{2/(1+y_n)}$ via some sort of Taylor series (which isn't hard using the Newton binomial theorem), and truncating this.
This gives us a recurrence relation "inequality", which will likely still be non-linear if we don't want to incur much error in the remainder term.
I've looked into things like this paper, but was unable to get my recurrence to fit into their framework (although it's quite close).
The related series:
$$ z_{n+1} = \frac{1}{\sqrt{1+z_n}}z_n,\quad z_0\in[0,1]$$
Seems to fit in, although the results I got from applying the technique of that paper to this recurrence were spotty at best (likely due to computational errors on my part, but I don't want to chase them down without being able to apply this technique to my recurrence).
Since $y_n$ converges to $1$ fairly quickly, I'm more interested in a tight bound for lower values of $i$ (for higher values, the bound $y_n\leq 1$ becomes increasingly tight).
It's unclear precisely what regime "low values" and "high values" mean, but interpreting it as "compared to $1/y_0$" (or potentially even $\log(1/y_0)$, I haven't done numerical investigations of this yet) is a safe bet.
I'm mostly interested in if there are any general techniques for bounding non-linear recurrence relations, in situations where the solutions appears to be highly "non-chaotic". I understand that it can be difficult to derive closed forms for non-linear recurrence relations, but I hope these dual relaxations (well-behaved solutions, and solely a close upper bound) make the problem more tractable.
Best Answer
Expanding on the idea from Somos's comment: define $x_n=1-y_n$, so that you want a lower bound on $x_n$. The recurrence becomes $$ x_{n+1} = 1-y_{n+1} = 1-\sqrt{\frac{2}{1+y_n}}y_n = 1-(1-x_n)\sqrt{\frac{2}{2-x_n}}. $$ Note that the function $1-(1-x)\sqrt{2/(2-x)}$ is larger than $\frac34x$ for all $x\in(0,1)$. Therefore $x_{n+1} \ge \frac34x_n$, and so by induction $x_n \ge (\frac34)^n x_0$. In other words, $y_n \le 1 - (\frac34)^n (1-y_0)$.
Of course you can start at $y_7$ (for example) instead of $y_0$ and get $y_n \le 1 - (\frac34)^{n-7} (1-y_7)$ for $n\ge7$; this will be helpful if your $y_0$ is not close to $1$—calculating $y_7$ by hand will be less wasteful than the above argument.