Re^2: Fibonacci, a generalization

[Richard Mathar]

gmg> From: Gerald McGarvey <Gerald.McGarvey at comcast.net>
gmg> Subject: Re: Fibonacci, a generalization
gmg> 
gmg> Emeric and seqfans,
gmg> 
gmg> It appears that if we substitute a value of x for the 4 in 1 + 
gmg> 4*cos(j*Pi/n)^2 below
gmg> than we get the sequence defined by the recurrence
gmg> a(0) = a(1) = 1, a(n) = a(n-1) + (x/4)*a(n-2).
gmg> Is this known?
gmg> 
gmg> For example
gmg>   0: all 1's
gmg>   4: Fibonacci numbers
gmg>   8: A001045 Jacobsthal sequence: a(n) = a(n-1) + 2a(n-2), starts as 0, 1, 
gmg> 1, 3, 5, ...
gmg> 12: A006130 a(n) = a(n-1) + 3a(n-2), a(0) = a(1) = 1
gmg> 16: A006131, a(n) = a(n-1) + 4*a(n-2)
gmg> 20: A015440, Generalized Fibonacci numbers, a(n) = a(n-1) + 5 a(n-2)
gmg> 
gmg> I first used this PARI code:
gmg> f(n,m) = p=1;for(j=1,ceil(n/2)-1,p=p*(1+m*cos(j*Pi/n)^2));return(p)
gmg> for(m=0,12,print1(m,":");for(n=1,10,print1(f(n,m),", "));print(" "))
gmg> 
gmg> then this code:
gmg> fr(n,m)=round(f(n,m))
gmg> for(m=0,24,print1(4*m,":");for(n=1,10,print1(fr(n,4*m),", "));print(" "))
gmg> 
gmg> Regards,
gmg> Gerald

These Horadam sequences of the form
a(n)=a(n-1)+k*a(n-2)
have the generating functions g(x)=1/(1-x-k*x^2)
if they are "normalized" to start with a(0)=a(1)=1 [otherwise, if starting
with a(0)=0 another factor of x appears in the numerator of g(x)].
See for example S.P. Pethe and R.M. Fernandes in
Ulam Quarterly Vol 3 No 1, 1995.
The generic term then becomes
a(n)= [(-1)^n/alpha^(n+1)-(-1)^n/beta^(n+1)]/D
where D=sqrt(4k+1), alpha= (1+D)/(2k), beta=(1-D)/(2k)

I suspect that the product formula of a(n)=product[...] is
a decomposition of formula (3.4) given by
Gheorghe Udrea, "A note on the sequence W_n (n>=0) of A.F. Horadam"
in Portugaliea Mathematica vol 53 (fasc 2) 1996
http://www.emis.ams.org/journals/PM/53f2/pmf53f203.pdf
in the sense of the product decomposition of 1.393 in the
book by Gradsteyn and Ryzhnik. I didn't work out any details.

The generic PARI code to cover these cases is:
a(n,k)={
        local(alpha,beta,dis) ;
        dis=sqrt(4*k+1) ;
        alpha = 1/(2*k)*(1+dis) ;
        beta = 1/(2*k)*(1-dis);
        return(((-1)^n/alpha^(n+1)+(-1)^(n+1)/beta^(n+1))/dis) ;
}

\\ 0, 1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365
\\ g.f. x/(1-x-3x^2)  (factor x because of offset)
A001045(n)={
        return( a(n,2)) ;
}

\\ 1, 1, 4, 7, 19, 40, 97, 217, 508
\\ g.f. 1/(1-x-3x^2)
A006130(n)={
        return( a(n,3)) ;
}

\\ 1, 1, 5, 9, 29, 65, 181, 441, 1165, 2929
\\ g.f. 1/(1-x-4x^2)
A006131(n)={
        return( a(n,4)) ;
}

\\ 1, 1, 6, 11, 41, 96, 301, 781, 2286
\\ g.f. 1/(1-x-5x^2)
A015440(n)={
        return( a(n,5)) ;
}

\\ 0, 1, 1, 7, 13, 55, 133, 463, 1261
\\ g.f. x/(1-x-6x^2) (factor x because of offset 0)
A015441(n)={
        return( a(n,6)) ;
}

{
        for(n=0,20,
                print(A001045(n)," ",A006130(n)," ",A006131(n)," ",A015440(n)," ",A015441(n)) ;
        ) ;
}


ed>At 10:40 AM 10/15/2006, Emeric Deutsch wrote:
ed>I did find it hidden in Fibonacci's Problem Book (M. Bicknell
ed>and V. E. Hoggatt, Jr, eds), pp. 47-48.
ed>
ed>Emeric
ed>
ed>
ed>On Sun, 15 Oct 2006, Emeric Deutsch wrote:
ed>
ed>>Dear Seqfan,
ed>>Is the following known?
ed>>
ed>>fibonacci(n)=Product(1 + 4[cos(j*Pi/n)]^2,  j=1..ceil(n/2)-1)
ed>>
ed>>Thanks,
ed>>Emeric