Solving a recursion efficiently I have a recursive formula $$v(n+1) = v(n)\dfrac{1+v(n-1)-n}{1+v(n-1)-v(n)}$$
and I also know $$v(1)=2v(0)$$ $$n+1 \le v(n+1) \le v(n)+1.$$
I wish to find, for example, $v(10)$ more efficiently than my current method does. That involves using the numerical instability of the recursion, by trying different values of $v(0)$, taking them forward until one of the inequalities is not met, then adjusting my estimate for $v(0)$ using a bisection method, and trying again.
If I use sufficient decimal precision (about $45$ decimal places in this example) for my calculations and search then I can get a value for $v(0)$ of about $0.6245357205\ldots$ which then gives a value for $v(10)$ of about $10.0000000114\ldots$.  
But this seems excessive, especially if I want $v(n)$ for larger $n$; I ended up finding $v(0)$ to $2000$ decimal places in http://www.se16.info/hgb/lockedbox.pdf
I was wondering whether there might be an alternative approach.
 A: 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?
