0
$\begingroup$

Is there a general way of evaluating the points in a recurrence relation when the initial conditions are not contiguous? For instance:

$T(i) = f\left(T(i-1), T(i-2)\right),$ with $T(a) = A$ and $T(b) = B$, and $a+1 \leq i \leq b-1$ (and with whatever $f$ and $a < b+1$).

I am concerned with the (possibly numeric) evaluation of $T(i)$, not with the solution of the above equation (since it has no closed-form solution in the general case).

If it is not possible in general, what about particular cases (other than $b$ = $a+1$ or $f$ "solvable").

2 Answers 2

0

If $f$ is simply linear, then you will typically find that the general solution looks like $T(i)=c_1\alpha_1^i+c_2\alpha_2^i$ (or in rare cases $T(i)=(c_1+c_2 i)\alpha^i$) with $\alpha_1, \alpha_2$ determined by the relation and $c_1, c-2$ freely chosable. In all but the most special casess, any two $T(i)$ will produce a solveable system of two linear equations in $c_1, c_2$.

If $f$ is not linear, one may still excpect that the set of solutions without initial conditions is somewhat two-dimensional. But whether solutions for given "initial" conditions exist or not depends a lot on specifics of $f$.

  • 0
    Thank you for your answer. However, I am not looking for solving the recurrence, but rather _evaluating_ the $T(i)$.2012-09-19
0

In the general case your recurrence boils down to a system of equations in the $T(i)$. You might try to solve that one directly (if the range isn't too big).

Another approach would be to start with the (known) $T(a)$, guess a $T(a + 1)$ and compute forward to $T(b)$. Use some iterative method (e.g. Brent's) to get the correct $T(a + 1)$.

If the recurrence has a particular form, it might be possible to solve it exactly (using methods similar to the ones that work for non-linear differential equations). Or you might apply some change of variable that makes it better behaved for some of the above techniques. Or approximate it by a differential equation, and solve that one...