# 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?