Are there programs out there that try to derive linear recurrence given a string of numbers? Wolfram isn't helping me much so I am curious if there are other programs out there.
I don't know what degree it is, but I have a series of numbers and I'd like to determine the linear recurrence function/coefficients so I can find any value I want via matrix exponentiation.
Are there such programs for interpolating, and how would I do it?
 A: You want the book The Book of Numbers by Conway and Guy. A description of the algorithm is at ALGORITHM but is not typeset. 
A: There are more powerful tools in Pari/GP, for example the LLL algorithm. Here is a small program that eats a vector of integers and spits out the rational generating function or 0 if it can't find it. Note that the coefficients of the denominator polynom determine the coefficients of the linear recurrence:
ggf(v)=local(l,m,p,q,B);l=length(v);B=floor(l/2);if(B<3,return(0));m=matrix(B,B,x,y,v[x-y+B+1]);q=qflll(m,4)[1];if(length(q)==0,return(0));p=sum(k=1,B,x^(k-1)*q[k,1]);q=Pol(Pol(vector(l,n,v[l-n+1]))*p+O(x^(B+1)));if(polcoeff(p,0)<0,q=-q;p=-p);q=q/p;p=Ser(q+O(x^(l+1)));for(m=1,l,if(polcoeff(p,m-1)!=v[m],return(0)));q

Example:
? ggf([1,3,7,15,31,63,127,255])
1/(2*x^2 - 3*x + 1)

So, $a_{n}=3a_{n-1}-2a_{n-2},$ starting $a_0=1, a_2=3$.
Note also that my program needs $2d$ values to determine the coefficients of a recurrence of order $d$. This is just to have a check on the result and could perhaps be optimized if really necessary.
Have fun.
