Simple Conjecture

[Franklin T. Adams-Watters]

Ralf Stephan <ralf at ark.in-berlin.de> wrote:
>> I would like to know if the conjecture made in the
>> comment, below, has already been proven or at least has
>> a name. 
>>...
>> Apparently (not sure if this is a conjecture or has been proven 
>> by someone else) if (z(n)) is any sequence of integers (not all zero) 
>> satisfying the forumla z(n) = 2(z(n-2) - z(n-1)) + z(n-3) then 
>> |z(n+1)/z(n)| -> golden ratio phi + 1 = (3+sqrt(5))/2 
>
>This is easy to prove. Such sequences have the g.f. P(x)/(1+2x-2x^2-x^3)
>and the denominator has the factors 1-x and 1+3x+x^2. Thus, the closed
>form involves a constant term plus sequences satisfying
>a(n+2)=-3a(n+1)-a(n) which are of form c*r^n+d*s^n with r,s the roots
>of 1+3x+x^2.

Actually, not quite: the conjecture as stated is false.  That x-1 factor means that any constant sequence satisfies the recurrence (this can be seen to be obviously true from looking at the recurrence).  It is true that any non-constant sequence satisfying the recurrence will approach phi+1 in the limit, for the reasons outlined by Ralf.

>The C-finite universe is quite boring after time, you can even churn
>out the closed forms automagically with a little help of LLL.
-- 
Franklin T. Adams-Watters
16 W. Michigan Ave.
Palatine, IL 60067
847-776-7645


__________________________________________________________________
Switch to Netscape Internet Service.
As low as $9.95 a month -- Sign up today at http://isp.netscape.com/register

Netscape. Just the Net You Need.

New! Netscape Toolbar for Internet Explorer
Search from anywhere on the Web and block those annoying pop-ups.
Download now at http://channels.netscape.com/ns/search/install.jsp