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

franktaw at netscape.net franktaw at netscape.net
Sun Aug 2 22:07:57 CEST 2009

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

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.

```