# [seqfan] (no subject)

Richard Mathar mathar at strw.leidenuniv.nl
Sun Aug 2 13:03:39 CEST 2009

```rh> From seqfan-bounces at list.seqfan.eu Sun Aug  2 12:43:27 2009
rh> Return-Path: <seqfan-bounces at list.seqfan.eu>
rh> From: rhhardin at att.net
rh> To: seqfan at list.seqfan.eu
rh> Date: Sun, 02 Aug 2009 10:15:13 +0000
rh> Subject: [seqfan]  LRS formulas for n>=...?
rh>
rh> In for example the (one of many, new) three combinatoric sequences offset=1
rh>
rh> 1,2,5,9,17,39,95,217,473,1011,2147,4545,9601
<snip>
rh>
rh> 6,21,48,108,236,506,1080,2294,4854,10248
<snap>
rh>
rh> one can find the same empirical formula
rh>
rh> 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
rh>
rh> Are such formulas of interest?  I don't see any like them offhand in EIS.

The interest is in figuring out which other sequences have
the same combinatorial structure. To make such connection, one needs to gather
them at some common market place like
http://research.att.com/~njas/sequences/Sindx_Rea.html#recLCC
(for which I have some slightly updated version).  The idea is that a look-up
with the (4,-5,2,1,-2,1) signature of the coefficients coeff(i) in front of
the a(n)=sum_i coeff(i)*a(n-i) leads to other sequences of the same family.

Another side effect is that one can write down the ordinary generating
function then (or its conjectured form if the recurrence is conjectural).
If the denominator polynomial then splits, one gets a very quick estimate to
whether the first differences, partial sums, Binomial transforms etc
are "simple." In the cases above, for example:

1,2,5,9,17,39,95,217,473,1011,2147,4545,9601:
(-1+2*x-2*x^2+3*x^3-x^4-6*x^5-4*x^6+3*x^7+2*x^8)/(x^4+2*x-1)/(x-1)^2
=
2*x^2+7*x+8-2/(x-1)^2+(-12*x^2-10*x+6)/(x^4+2*x-1)-1/(x-1)

6,21,48,108,236,506,1080,2294,4854,10248,21614:
(1+x)*(2*x^7-x^6-7*x^5+10*x^4-6*x^3-3*x^2+9*x-6)/(x^4+2*x-1)/(x-1)^2
=
2*x^2+5*x+(-9*x^3-9*x^2-x-11)/(x^4+2*x-1)-2/(x-1)^2+3/(x-1)

3,11,28,63,138,298,642,1371,2908,6146,12970,27351,57654,121502,256026:
(-3+x+x^2-x^4-5*x^6+x^7+2*x^8)/(x^4+2*x-1)/(x-1)^2
=
2*x^2+5*x+3+2/(x-1)+(-5*x^3-10*x^2-4*x-4)/(x^4+2*x-1)-2/(x-1)^2

Richard Mathar

```