# [seqfan] Re: Bivariate recurrence leading to univariate one with sqrt()

Max Alekseyev maxale at gmail.com
Thu Mar 3 07:14:25 CET 2011

```Actually, the formula for a(n) can be simply stated as

a(n) = n * 2^floor(log(n)/log(2)) = n * A053644(n).

There are also explicit formulas for A097051 and A097053:

If floor(log_2(n))=2k+1, then A097051(n) = floor(n/2^k). If
floor(log_2(n))=2k, then A097051(n) = 2^k.

For n>1, A097053(n) = A053644(n) * n / 2.

Regards,
Max

On Tue, Mar 1, 2011 at 8:10 PM, Max Alekseyev <maxale at gmail.com> wrote:
> There is a simple formula:
>
> T(i,j) = i * 2^floor(log(j)/log(2)), if i not a power of 2;
> T(i,j) = i * j, otherwise.
>
> Correspondingly,
>
> a(n) = n * 2^floor(log(n)/log(2)), if n is not a power of 2;
> a(n) = n^2, otherwise.
>
> Regards,
> Max
>
> On Tue, Mar 1, 2011 at 2:46 PM, Georgi Guninski <guninski at guninski.com> wrote:
>> Define the efficiently computable bivariate recurrence:
>> T(i,j)=j if i<=1
>> T(i,j)=i if j<=1
>> T(i,j)=2*T(i/2,j) if i mod 2 = 0
>> T(i,j)=2*T(i,floor(j/2)) otherwise
>>
>> and a(n)=T(n,n)
>>
>> Empirically a(n) satisfies the univariate recurrence with offset 0:
>>
>> if n != 2^k and n != 2^k+1
>> a(n)=-1/2*sqrt(36*(a(n - 3) - 2*a(n - 2))*a(n - 1) + 28*a(n - 3)^2 - 108*a(n - 3)*a(n - 2) + 105*a(n - 2)^2 + 12*a(n - 1)^2) - 3*a(n - 3) + 9/2*a(n - 2)
>> else
>> a(n)=1/2*sqrt(36*(a(n - 3) - 2*a(n - 2))*a(n - 1) + 28*a(n - 3)^2 - 108*a(n - 3)*a(n - 2) + 105*a(n - 2)^2 + 12*a(n - 1)^2) - 3*a(n - 3) + 9/2*a(n - 2)
>>
>> For the first 510 terms a(n+1)=2 A097053(n) for n>2
>>
>> superseeker finds generating function with somewhat large coefficients.
>> fricas finds strangely looking ADE.
>>
>> The sequence starts:
>> 1, 1, 4, 6, 16, 20, 24, 28, 64, 72, 80, 88, 96, 104, 112, 120, 256, 272, 288
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>

```