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

Max Alekseyev maxale at gmail.com
Tue Mar 1 18:10:03 CET 2011

```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/
>

```

More information about the SeqFan mailing list