right-half-sum triangle - Recursion

[Paul D. Hanna]

Hi Max,
      My method here is not sophisticated, and no doubt you would have
found the formula in due time. 
 
Knowing that the partial sums in each row multiplies the prior row g.f.
by 1/(1-x), 
I was looking for a linear recurrence involving binomial coefficients in
1/(1-x)^n 
at positions 2^m-2^k (as I indicate in the table below). 
1,2, 3, 4, 5,  6,  7,  8,  9, 10,  11,  12,  13,  14,   15,   16, 
1,3, 6,10,15, 21, 28,(36),45, 55,  66,  78,  91, 105,  120,  136,
1,4,10,20,35, 56, 84,120,165,220, 286,(364),455, 560,  680,  816,
1,5,15,35,70,126,210,330,495,715,1001,1365,1820,(2380),3060,[3876],
 
In the above table of binomial coefficients, we see that:
a(5) = 516 = 3876 - (1*2380 - 2*364 -7*36)
 
I do not have time now, but I will try to provide the details to you Max,

and to anyone else upon request. 
 
Paul
 
On Tue, 24 May 2005 22:14:12 -0700 Max <relf at unn.ac.ru> writes:
> Wow!
> How did you find this formula?
> 
> Thanks,
> Max

> > a(0)=1
> > 
> > a(n) = C(2^(n-1)+n-2,n-1) - Sum_{k=1..n-2} 
> a(k)*C(2^(n-1)-2^k+n-k-1,n-k)
> > 
> > where C(n,k)=binomial(n,k).