right-half-sum triangle - Recursion

[Max]

Wow!
How did you find this formula?

Thanks,
Max

Paul D. Hanna wrote:
> Dear Max and Seqfans,
>        As Ralf indicated, a closed form may not exist ... 
> but here is a nice recursion: 
> 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).
> 
> EXAMPLE.
> a(5) = 516 = C(19,4) - ( 1*C(17,4) + 2*C(14,3) + 7*C(9,2) )
> = C(16+4-1,4) - (1*C(16-2+4-1,4) + 2*C(16-4+3-1,3) + 7*C(16-8+2-1,2) ).
> 
> PARI CODE.
> {a(n)=if(n==0,1,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)))}
>  
> Nice sequence.
>       Paul
>  
> On Mon, 23 May 2005 18:39:01 -0700 Max <relf at unn.ac.ru> writes:
> 
>>Hello!
>>
>>I'm going to add the following sequence to OEIS.
>>
>>1 1 2 7 44 516 11622 512022 44588536 7718806044 2664170119608 
>>1836214076324153 2529135272371085496 6964321029630556852944 
>>38346813253279804426846032 422247020982575523983378003936 
>>9298487213328788062025571134762096
>>
>>which is computed as follows.
>>
>>To compute a(n) we first write down 2^n units in a line. Each next 
>>line takes the right half of the previous, and each element in it 
>>equals sum of the elements above starting with the middle. The only 
>>element in the last line is a(n).
>>
>>For example, for a(4) computed "triangle" looks like:
>>
>>   1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1
>>   .  .  .  .  .  .  .  .  1  2  3  4  5  6  7  8
>>   .  .  .  .  .  .  .  .  .  .  .  .  5 11 18 26
>>   .  .  .  .  .  .  .  .  .  .  .  .  .  . 18 44
>>   .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 44
>>
>>Therefore, a(n)=44.
>>
>>I'm mostly interested in a closed formula for this sequence.
>>Do you have any idea how to find it?
>>
>>Thanks,
>>Max
>>
>>
> 
> 
>