Solving a recursion efficiently
Suggested Improvement for Algorithm
I hope I understand the question correctly. My interpretation is as follows:
Question: Given some $n$, we want to find a good* approximate value for $v_n$, where $v_n$ is defined as above.
Algorithm
We start of with some "reasonable" approximation for $v_0$- just to a few decimal places is all we need. Now we initialise an interval to $[n, n+v_0]$. From below we know that $v_n$ must lie in this range. From here, iterate with the following.
Set $v_n$ to the midpoint of the interval.
Compute the recurrence forward until it fails, high or low, note the number of steps it took to fail as $k$.
If $k$ is sufficiently big, then stop.
Else note the direction of failure, chop the interval accordingly, and return to the first step.
Notes
This is essentially the same as the method given, with one major difference: we start with an approximation of $v_n$, not $v_0$. This way, we do not waste time on tiny perturbations in the value of $v_0$ that quickly lead to large disturbances. In fact we never fail the test for $v_n$, because we start with an approximation for $v_n$ in the known range. Arguably then this is a better approach than starting at $v_0$, though it really depends on what is meant by a "good" approximation- see below. It also depends on my interpretation of the question. Certainly it lacks an explicit error term.
For this method, we don't need a massively accurate approximation of $v_0$ to begin with. It would be overkill. This is because we're going to chop the interval $[n, n+v_0]$, so fine-tuning $v_0$ seems pointless. However, after glancing at the linked pdf, I do worry somewhat about the term $u_n = v_n - n$, which seems to tend towards zero by a factor of $\frac1{n!}$. In this case, starting at the midpoint of $[n, n+v_0]$ seems a bit foolish, and we'd really be better starting much closer to $n$. I did not think further about this though, as I do not know where the inverse factorial relationship originates, so I leave it up to the questioner to investigate this issue.
*The definition of "good" is a bit hazy here. The standard interpretation would be an error, absolute or percentage, from the "true" value (if it is unique). However, the approach I take here follows the style of the questioner. We say that an approximation is good to $k$ steps for $v_n$ if the following $k$ terms $v_{n+1}$ up to $v_{n+k}$, computed via the recurrence, respect the inequalities given. Another interpretation would be to also take some terms before $v_n$, computing the recurrence backwards, but I'll leave this for later work.
Some old Observations
$v_0 \geq 0$. Otherwise, $v(1)=2v(0)$ would be negative, contradicting the second condition, in particular $n + 1 \leq v_{n + 1}$, which for $n=0$ gives $1 \leq v_1$.
For all natural numbers $n$, including $0$, we have that $n \leq v_n \leq n + v_0$. This follows from the second condition and a little bit of induction.
$v_n$ is monotonically increasing, from the last condition and the experimental fact that $0 < v_0 < 1$
A question I would ask is: does a non-trivial, exact, solution exist? If so, is it unique?