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

[Roland Bacher]

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
 2(log(a[m])+log(a[m-1])+...)/log(a[m])=2(1+1/s+1/s^2+..)=2/(1-1/s)=s
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.