[seqfan] Re: Linear recurrences with large gaps

[Joerg Arndt]

* Ron Hardin <rhhardin at att.net> [Jan 11. 2011 13:28]:
> Rows of  http://oeis.org/A184257
> T(n,k)=Number of strings of numbers x(i=1..n) in 0..k with sum i^3*x(i) equal to 
> n^3*k

Soemwhat easier (?) to read:
"Number of length-n strings of numbers ..."
Admittedly bit redundant.

> seem to have linear recurrences with large gaps
> 
> http://oeis.org/A184258
> Number of strings of numbers x(i=1..3) in 0..n with sum i^3*x(i) equal to 27*n
> Empirical: a(n)=2*a(n-1)-a(n-2)+a(n-27)-2*a(n-28)+a(n-29)
> 
> http://oeis.org/A184259
> Number of strings of numbers x(i=1..4) in 0..n with sum i^3*x(i) equal to 64*n
> Empirical: 
> a(n)=2*a(n-1)-a(n-2)+a(n-8)-2*a(n-9)+a(n-10)+a(n-64)-2*a(n-65)+a(n-66)-a(n-72)+2*a(n-73)-a(n-74)
> 
> 
> probably for some simple reason that hasn't occured to me yet.
> 

Note the factorization:

? p=-1+2*a^1-a^2+a^8-2*a^9+a^10+a^64-2*a^65+a^66-a^72+2*a^73-a^74
-a^74 + 2*a^73 - a^72 + a^66 - 2*a^65 + a^64 + a^10 - 2*a^9 + a^8 - a^2 + 2*a - 1
? factor(p)
[a - 1 4]
[a + 1 2]
[a^2 + 1 2]
[a^4 + 1 2]
[a^8 + 1 1]
[a^16 + 1 1]
[a^32 + 1 1]

/* == */
? -(1-a)^2*(1-a^8)*(1-a^64)
-a^74 + 2*a^73 - a^72 + a^66 - 2*a^65 + a^64 + a^10 - 2*a^9 + a^8 - a^2 + 2*a - 1

Is the recurrence complete?
Else more terms could pop up, so that the recurrence really would be
 -(1-a) * prod(n=0, infinity, (1-a^(8^n)) )

This is a a lacunary product:  e.g., for infinity=3:
a^586 - 2*a^585 + a^584 - a^578 + 2*a^577 - a^576 - a^522 + 2*a^521 - a^520 + a^514 - 2*a^513 + a^512 - a^74 + 2*a^73 - a^72 + a^66 - 2*a^65 + a^64 + a^10 - 2*a^9 + a^8 - a^2 + 2*a - 1

> 
> 
>  rhhardin at mindspring.com
> rhhardin at att.net (either)
> 
> 
> _______________________________________________
> 
> Seqfan Mailing list - http://list.seqfan.eu/