q. about g.f.'s from a correspondent

[N. J. A. Sloane]

satisfies a QUADRATIC equation (examples: Catalan, Schroder, Motzkin,
Return-Path: <simon.plouffe at gmail.com>
X-Ids: 168
DKIM-Signature: a=rsa-sha1; c=relaxed/relaxed;
        d=gmail.com; s=beta;
        h=domainkey-signature:received:received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=JoDyR4aKfI/+Dt+xqZ0HgJuyCI1olAy9QmHkVfOOf5Li8IpWY4QNQJ1UZ4MlQsyGC3jXrZF7vsHIvNW9pHNWhG7A76N8atD1hb3jqdNDXk3+v+R4rFDM6DUjQ2cMzrK2KofF0J17RfRreAQo/M7alRmnmLKD0t0KufoN17jXRiQ=
DomainKey-Signature: a=rsa-sha1; c=nofws;
        d=gmail.com; s=beta;
        h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:content-transfer-encoding:content-disposition:references;
        b=rz2b6JRr0fYt85OR/JibAx2JcgJNXcyDq1+Ah23uWjDpT5FLnpwhLPi4DlnbNSPy80w12k1mAW30v2Um8UwcneG3ZBjQ1SJUUK94JDEoYG0HI0+4JUFE3NzPP0X3Ip5Ox3U7q9YjVVIKudcD8UqaPRoYY7RetNUfpSNyKJyVnXI=
Message-ID: <33a322bc0703021059m79ef6aeexb78e84fcfd020bf0 at mail.gmail.com>
Date: Fri, 2 Mar 2007 13:59:40 -0500
From: "Simon Plouffe" <simon.plouffe at gmail.com>
To: njas at research.att.com
Subject: Re: q. about g.f.'s from a correspondent
Cc: seqfan at ext.jussieu.fr
In-Reply-To: <200703021807.NAA23953 at fry.research.att.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <200703021807.NAA23953 at fry.research.att.com>
X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-2.0.2 (shiva.jussieu.fr [134.157.0.168]); Fri, 02 Mar 2007 19:59:48 +0100 (CET)
X-j-chkmail-Score: MSGID : 45E87420.000 on shiva.jussieu.fr : j-chkmail score : X : 0/50 1 0.486 -> 1
X-Miltered: at shiva.jussieu.fr with ID 45E87420.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!

Hello,

There is no simple answer but there is a way to have some
sequences.

A sequence can satisfy a linear rec. with polynomial coefficients
or not (at least detectable with GFUN or RATE). If it does
satisfy a rec then it may also satisfy a quadratic equation or a cubic
equation.

But to have a criteria upon looking at a sequence and say 'this sequence
satisfies an algebraic equation of degree 2 or 3 : there is no
general procedure.

So it has to be a LRPC (lin rec with pol coeff.) first and then it
may or may not be algebraic, unfortunately that does not
necessary makes things easier since there are apparently no
way to tell by advance of which degree the algebraic equation will
be.

I propose this approach : scan the OEIS database for LRPC first
and then (if it has been detected) there might be an algebraic equation
for it.
You may look at this document to help you understand
the difficulty of solving LRPC's in general :

http://www.lacim.uqam.ca/~plouffe/articles/FlorencealgebraicLLL.pdf

this was written in 1992, maybe someone solved the general
problem ??

Simon Plouffe



Hello seqfans,

I collected in one place the sequences that pass the recursion test, but it is not clear from their description if they are recursions:

http://www.tanyakhovanova.com/RecursiveSequences/NonRecursions.html

These are exactly the sequences that were excluded from 
http://www.tanyakhovanova.com/RecursiveSequences/RecursiveSequences.html

Here are some of these sequences:
A078642 a(n) = a(n-1)+a(n-2), a(0) = 4, a(1) = 6. Numbers with two representations as the sum of two Fibonacci numbers. 
A081808 a(n) = 2*a(n-1), a(0) = 12. Numbers n such that the largest prime power in n factorization equals phi(n).
A044322 a(n) = a(n-1) + 81, a(0) = 71. Numbers n such that string 7,8 occurs in the base 9 representation of n but not of n-1.
A088475 a(n) = a(n-1) + 1, a(0) = 10. Numbers n such that dismal sum of prime divisors of n is ≥ n.

It would be nice if someone who knows these sequences better can add comments to these sequences (either that they are in fact recursions or the first place where it breaks)

Tanya
P.S. Thank you for all feedback I received on my recursive sequences page


_________________________________________________________________
Need personalized email and website? Look no further. It's easy
with Doteasy $0 Web Hosting! Learn more at www.doteasy.com