Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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").

share|improve this question
add comment

2 Answers

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$.

share|improve this answer
    
Thank you for your answer. However, I am not looking for solving the recurrence, but rather evaluating the $T(i)$. –  doc Sep 19 '12 at 15:20
add comment

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...

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.