[seqfan] Re: Paraffin Numbers

Charles Greathouse charles.greathouse at case.edu
Sun Mar 11 17:45:41 CET 2012


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

Yes, that would be nice.

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

I've had a program to do this on the OEIS wiki for some time:
https://oeis.org/wiki/User:Charles_R_Greathouse_IV/Pari
It's inefficient, but that doesn't matter if the recurrence is less
than order, say, 40.  A more efficient version would use PARI's LLL
via qflll.

Some languages have these commands built-in, like Mathematica's
FindLinearRecurrence.

Charles Greathouse
Analyst/Programmer
Case Western Reserve University

On Sun, Mar 11, 2012 at 12:30 PM, David Wilson <davidwwilson at comcast.net> wrote:
> 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.



More information about the SeqFan mailing list