A002449 as Solution to System of Equations?

[Dean Hickerson]

Mostly to Paul D. Hanna:

> Help is needed to simplify the following problem.
>  
> Consider the infinite system of simultaneous equations:
> A = 1 + xAB
> B = 1 + xBCD
> C = 1 + xCDEF
> D = 1 + xDEFGH
> E = 1 + xEFGHIJ
> F = 1 + xFGHIJKL
> ... 
> What is the unique solution to the variables A,B,C,... as functions in x?

First, they're not really functions, since the power series don't converge
for x!=0.  But the question makes sense for formal power series.

Let a(1) = A, a(2) = B, a(3) = C, ...  Then the equations say that

    a(n) = 1 + x a(n) a(n+1) ... a(2n)

for n>=1.  Let p(n) be the product a(1)*...*a(n); in particular p(0) = 1.
Then

    p(n) = p(n-1) + x p(2n).

Now let p(n) = sum_{i>=0} c(n,i) x^i.  The c's can be computed by
the recurrence

    c(n,i) = c(n-1,i) + c(2n,i-1)    for n>=1, i>=1,

with the initial conditions

    c(n,0) = 1    for n>=0,

    c(0,i) = 0    for i>=1.

Since A = a(1) = p(1), you want the terms c(1,i).

As you said, computing c(1,i) takes about 2^i steps.  But it turns out
that, for fixed i, c(n,i) is a polynomial in n, of degree i:

    c(n,i) = sum_{0<=j<=i} d(i,j) n^j.

Getting a recurrence for the d's is straightforward but messy.  (I.e. it
took me a few tries to get it right.)  We find:

    d(0,0) = 1,

    d(i,0) = 0    for i>=1,

and

    d(i,j) = 1/j [2^(j-1) d(i-1,j-1) -
             sum_{j+1<=m<=i} (-1)^(j+m) binomial(m,j-1) d(i,m)]   for 1<=j<=i.

Using this, we can compute the c's much more quickly.  In Mathematica:

    d[0,0]=1;
    d[i_,0]:=0;
    d[i_,j_]:= d[i,j] = 1/j (2^(j-1) d[i-1,j-1] -
                        Sum[(-1)^(j+m) Binomial[m,j-1] d[i,m], {m,j+1,i}] );

    c[0,i_]:=d[i,0];
    c[n_,i_]:=Sum[d[i,j] n^j,{j,0,i}];

    Table[c[1,i],{i,0,20}]

produces:

    {1, 1, 2, 6, 26, 166, 1626, 25510, 664666, 29559718, 2290267226,
    314039061414, 77160820913242, 34317392762489766, 27859502236825957466,
    41575811106337540656038, 114746581654195790543205466,
    588765612737696531880325270438, 5642056933026209681424588087899226,
    101386818783417634431603640258454473638,
    3428771170016237895796931111337071731946586}

> Could someone calculate more coefficients of A 
> to see if they continue to agree with A002449? 

They agree at least up to A002499(50).

Dean Hickerson
dean at math.ucdavis.edu