a[m+1]=product{k=1 to m}(a[k]+a[m+1-k])

Roland Bacher Roland.Bacher at ujf-grenoble.fr
Mon Sep 6 08:48:59 CEST 2004

On Sun, Sep 05, 2004 at 06:24:46AM -0600, Leroy Quet wrote:
> Let a[1] =1,
> let a[m+1] = product{k=1 to m} (a[k] + a[m+1-k]).
> The sequence begins:
> 1,2,9,400,19456921,...
> and is sequence A049299 of the EIS.
> What is the limit, as m->infinity, of log(a[m+1])/log(a[m]) ?
> It appears to be about 3.
> (I wondered back in 1999 about this, but I will bring up the question 
> again now with seq.fan.)
> Thanks,
> Leroy Quet

The limit s=lim_{m\rightarrow\infty}
log(a[m+1])/log(a[m]) exists and equals indeed 3:

Sketch of proof:

The sequence is increasing very fast and we have thus for k>m+1-k
(a[k]+a[m+1-k])\sim a[k]

We get thus

a[m+1]\sim a[m]^2 * a[m-1]^2 * .... (each "big" factor comes roughly
twice: a[m] comes once from k=m and once from k=1).

taking logs we get thus
which yields s=3.

We have yet to show existence: It follows from the upper bound
a[m+1]<2^m  *  (product{k=1 to m} a[k]   )^2   
(in fact cum grano salis: 
a[m+1]<2^m  *  (product{k=[m/2] to m} a[k]   )^2   
where [m/2] is the integer part).

PS: you can put strictly positive weights w(m,k) and consider 
product{k=1 to m} (w(m,k) * a[k] + w(m,m+1-k) * a[m+1-k]) .

If the functions w(m,k) don't grow or decay to fast (not faster
than polynomially in n,k should certainly work), 
you will always get 3 in the above limit. 

More information about the SeqFan mailing list