Solving for a recurrence relationship of an integer sequence

Suppose you have a sequence of n numbers, it is known that there is one polynomial of degree n-1 that goes through those numbers as if they were y values when the x values were 1,2,3,n.. In the last post I discovered that those polynomials can be written as a recurrence: relationship satisfying:
-A*a(n)+B*a(n-1)-C*a(n-2)... = 0
where the coefficients A,B,C,... are row n+2 of Pascals Triangle...

But of course there are many series that if you fit a polynomial of degree n-1 through n points, that polynomial fails to accurately model the value of the n+1th point. One such series is the Fibonacci series...
1,1,2,3,5,8,13
I found that it's easy to find the correct recurrence formula for this series by:

Since we have eight points we look for a recurrence over the last n/2 or 4 terms, we consider that some a,b,c,d coefficients multiplying the first four terms will equal the 5th, those same a,b,c,d multiplying the 2-5th terms will equal the 6th etc. 

But looking at the recurrence formula this finds we see that d is a free variable, this means we can set it to 0 and get:

No we see that c has a variable b in it's form,  what it equals that can be set to 0 as well by making b=1.

Which gives the recurrence a(n) = 1*a(n-1)+1*a(n-2) which is the definition of the Fibonacci sequence. 

So we can look at any n numbers this way, here is one I thought of that wasn't already on the Encyclopedia of Integer sequences...

1, 3, 7, 10, 15, 23, 32, 53

If these values had been 4, -6, 4, -1 (a row on Pascals triangle with alternating signs) or it was possible through free variables to make it that, we would know that there was a cubic equation that plotted the values. Also if they could be 2, -2, 1 then a quadratic and so on. 

This one doesn't have a free variable which indicates that if there is a recurrence formula for this series it relies on at least the last 4 terms, also if there is a polynomial through the eight points it must be degree 4 or higher.  

And its predicted the next value isn't an integer, but it still gives a good guess for using 8 points. We could have also done the 9th degree polynomial through the eight points which gives:

If we had hundreds of points finding the polynomial through them gets very expensive, (exponential), while solving a set of n linear equations as in this method I've found is about O(n^3)

Another example from the Encyclopedia of Integer Sequences is the triangular numbers...
0, 1, 3, 6, 10, 15, 21, 28
Using this method this will yield the recurrence...
a(n) = 3*a(n-1)-3*a(n-2)+a(n-3)
which is the nice one found by Mark Dole in 2010.