[seqfan] Re: Paraffin Numbers

[David Wilson]

Parrafin numbers sequences are examples of linear recurrences.

Linear recurrences have many equivalent forms (these do not describe the 
same function):

     - As a recurrence which is a linear combination of previous terms:
         a(n) = 7a(n-1) - 6a(n-2) + a(n-3)

     - As a sum of terms which are a polynomial times a power of a constant:
         a(n) = (x^2+3) * 3^n + (x-5) * 3^n + (x^2-x+1) * 1^n  + 5 * (-1)^n

         As special cases, polynomials and powers of constants are 
themselves linear recurrences.

     - As a function whose generating function is a rational function 
(quotient of polynomials):
         gf_a(x) = (1-x^2+x^4)/((1-x)(1-x^2)(1-x-x^2))

     - As the value of a fixed element of matrix M(n) = PQ^n, where P 
and Q are constant matrices.

Linear recurrences have many nice closure properties:

     - The sum of two linear recurrences is a linear recurrence.
     - The product of two linear recurrences is a linear recurrence.
     - The running sum of two linear recurrences is a linear recurrence.
     - The convolution of two linear recurrences is a linear recurrence.
     - The regular interleaving of two or more linear recurrences is a 
linear recurrence.

Once you have played with linear recurrences for a while, you develop a 
sense for them (as I like to put it, I can often "smell" when a sequence 
is a linear recurrence).

Looking at your formula for A006009:

     a(n) = Sum(i = 1..n, (i + 1)*[(i + 1)^2/2])

I see it is the running sum of function

     f(n) = (n + 1)*[(n + 1)^2/2]

I see that this is the interleaving to two polynomial functions on odd 
and even arguments:

     f(2n) = (2n + 1)*(2n^2 + 2n)
     f(2n + 1) = (2n + 2)*(2n^2 + 4n + 2)

These are each polynomial in n, so they are linear recurrences. 
Interleaving these gives f, so f is a linear recurrence. a is the 
running sum of f, so a is a polynomial recurrence.

If you look at A006009 in the database, you see a rational generating 
function, and a program which gives A006009 as a fixed element of the 
power of a matrix. These two representations each confirm that A006009 
is a linear recurrence. Your function is a linear recurrence as well, 
which bodes well for its being a correct formula.

A formal proof that your formula is correct could be done by converting 
your formula and the generating function to linear recurrence form and 
seeing if they agree. This is probably not worth the effort.

A006009 is a linear recurrence of degree at most 7 (the generating 
function has a degree-8 denominator polynomial, but there is an 
unreduced factor of (1-x), so it is really degree-7). Likewise, your 
formula is the running sum of the interleaving of two degree-6 
polynomials, so it is around the same degree. So your formula is certain 
correct if it agrees with, say, 16 sequence elements.

Aside:

Theoretically, it would be possible to write a program that, given one 
of the linear recurrence forms (recurrence, generating function, 
formula, matrix description) could generate the others. It is also be 
possible to programmatically guess a linear recurrence for a sequence (I 
am guessing this is what Dr. Plouffe did to get his nice list of 
generating functions).

On 3/11/2012 6:01 AM, Simon Plouffe wrote:
>
> Hello,
>
>  Most of the formulas for the paraffins where found a while ago
> (1992). here :
> http://arxiv.org/ftp/arxiv/papers/0911/0911.4975.pdf
>
> see page 448 and forward there are dozen of related formulas
> for paraffins using infinite products.
>
>  Best regards,
>  Simon Plouffe
>
>
> Le 11/03/2012 10:24, Psychedelic Geometry a écrit :
>> Hello:
>>
>> The following Mathematica code seems to generate sequence A006009: 
>> Number of
>> paraffins.
>>
>> A006009[n_] := Sum[(i + 1)*Floor[(i + 1)^2/2], {i, 1, n}];
>>
>> And if this conjecture is correct then the Alkane (or paraffin) numbers
>> l(7,n) should be:
>>
>> A005994[n_] := Sum[(i + 1)*Floor[(i + 1)^2/2], {i, 1, n}]/2 - 
>> Binomial[n +
>> 3, 4];
>>
>>
>>
>> Does anybody knows how to prove o disprove these formulas?
>>
>>
>> Best Regards, Enrique.
>>
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>