[seqfan] Re: LRS formulas for n>=...?

[franktaw at netscape.net]

It is important to note that a sequence has a linear recurrence like 
this if and only if it has a rational generating function.  In 
particular, turn a(n-k) into x^k, and reformulate into a polynomial.  
In this case, we get:

1 = 4x - 5x^2 + 2x^3 + x^4 - 2x^5 + x^6,

which becomes the polynomial

1 - 4x + 5x^2 - 2x^3 - x^4 + 2x^5 - x^6.

This, then, is the denominator of the g.f.  Since the recurrence holds 
for n >= 10, the numerator will have degree < 10; this can then be 
calculated as long as enough terms are known.

One can go further and express the sequence in terms of powers of the 
roots of this (denominator) polynomial, but I'm not going to get into 
that any further here.

(This is fairly elementary stuff, and many of those who have been 
participating in this discussion are familiar with it.  It seems likely 
to me that there are some who do not, however.)

-----
For those for whom this stuff is old hat, there is a tendency to 
include the g.f. when they know it, but not to also add the explicit 
recurrence.  After all, one can just read off the recurrence from the 
g.f., but going the other way requires some calculating.

Franklin T. Adams-Watters

P.s. The word is combinatorial, not combinatoric.

-----Original Message-----
From: rhhardin at att.net

In for example the (one of many, new) three combinatoric sequences 
offset=1

1,2,5,9,17,39,95,217,473,1011,2147,4545,9601,20255,42703,90001,189657,399
627,842019,1774105,3737937,7875575,16593247,34960681,73659385,

6,21,48,108,236,506,1080,2294,4854,10248,21614,45564,96028,202354,426376,
898374,1892838,3988096,8402638,17703724,37300364,78588906,

3,11,28,63,138,298,642,1371,2908,6146,12970,27351,57654,121502,256026,539
459,1136632,2394830,5045754,10631039,22398786,47192482,99430802,

one can find the same empirical formula

a(n)=4*a(n-1)-5*a(n-2)+2*a(n-3)+a(n-4)-2*a(n-5)+a(n-6) for n>=10

Are such formulas of interest?  I don't see any like them offhand in 
EIS.