Closed form of two-layer recurrence

Question

I am trying to find a closed-form expression for $A(0)$, described by the following recurrence forms, as a function of $L$ and $d$:

\begin{align} A(\ell) &= 1 + 2^d A(\ell+1) + \sum_{g=0}^{d-1} \binom{d}{g} B(\ell+1,g) , \\ B(\ell,g) &= 1 + \sum_{j=0}^g \binom{g}{j} B(\ell+1,j) , \end{align}

with the termination conditions

\begin{align} A(L) = 0 , && B(L,g) = 0 , \;\; \forall g . \end{align}

I have tried the following approach but have had no luck with it:

recurB = (B[l,g] == 1 + Sum[ Binomial[g,j] B[l+1,j], {j,0,g} ]);
recurA = (A[l] == 1 + 2^d A[l+1] + Sum[ Binomial[d,g] B[l+1,g], {g,0,d-1} ]);
termB  = (B[L,_] == 0);
termA  = (A[L] == 0);
RSolve[ {recurB, recurA, termB, termA}, {A[l],B[l,g]}, {l,g} ]

It appears that the way I am trying to input the forms to Mathematica is not correct, but I have not managed to figure out how I should do it by looking at the documentation or other posts in SE.

I have also tried a few variations of the above code snippet---change $A(\ell+1)$ to $A(\ell-1)$ and $A(L) \leftrightarrow A(0)$ (similarly for $B$), or solve for only $B$ first and then use that form to solve for $A$---to no avail.

I am pretty new to Mathematica, so any help is appreciated!

---

UPDATE: a different (failed) approach

I have also tried the following, which does not entail the use of RSolve:

B[l_,g_] := 1 + Sum[ Binomial[g,j] B[l-1,j], {j,0,g} ];
B[0 ,_ ] := 0;
A[l_] := 1 + 2^d A[l-1] + Sum[ Binomal[d,g] B[l-1,g], {g,0,d-1} ];
A[0 ] := 0;
A[L]

but get the following error message:

$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation of -1021+L. >>

Answer 1

I haven't find a way to solve the problem using Mathematica straight away, but we can use it to navigate the formulas and for finding the relevant closed expressions. Please beware that the following is far from a formal proof and only an educated guess (how well "educated" is a matter of discussion, though :)

At the end of this post you'll find a self-consistency numeric experiment, i.e. by using the guessed closed forms, if you start with the A[0] value we will find next, you arrive at A[L]==0 after using the recurrence relations.

---

If we define

B[L, _] := 0;
B[l_, g_] := 1 + Sum[Binomial[g, j] B[l + 1, j], {j, 0, g}]

then:

FindSequenceFunction /@ Table[B[L - n, g], {n, 1, 7}, {g, 15}]
(*
{1 &, 
 1 + 2^#1 &, 
 1 + 2^#1 + 3^#1 &, 
 1 + 2^#1 + 2^(2 #1) + 3^#1 &, 
 1 + 2^#1 + 2^(2 #1) + 3^#1 + 5^#1 &, 
 1 + 2^#1 + 2^(2 #1) + 3^#1 + 5^#1 + 6^#1 &, 
 1 + 2^#1 + 2^(2 #1) + 3^#1 + 5^#1 + 6^#1 + 7^#1 &}
 *)

As 2^2==4 :) this means (first guess)

 B[L - n, g] == HarmonicNumber[ n, -g]

An that is a "closed form" for B[ ]

Now we have

 A[l] == 1 + 2^d A[l+1] + Sum[ Binomial[d, g] B[l+1, g], {g, 0, d-1} ]

And we will try to guess the Sum part:

Sum[ Binomial[d, g] B[l+1, g], {g, 0, d-1} ]

first,in order to use the closed form for B found above, we rewrite

l + 1 == L - (L - l - 1)

Then the sum is

Sum[Binomial[d, g] HarmonicNumber[L - l - 1, -g], {g, 0, d - 1}]

And again, we try to find a closed form with:

FindSequenceFunction /@ 
 Table[Sum[Binomial[d, g] HarmonicNumber[i, -g], {g, 0, d - 1}], {i, 1, 6}, {d, 1, 10}]

(* {-1 + 2^#1 &, -1 + 3^#1 &, -1 + 4^#1 &, -1 + 5^#1 &, -1 + 6^#1 &, -1 + 7^#1 &} *)

So it is (second guess)

  ourSum[i,d] -> -1 + (i+1)^d

Since in our actual sum i -> L -l -1, that means

  ourSum -> -1 + (L-l)^d

Replacing in the expression for A[l]

A[l] == 1 + 2^d A[l + 1] - 1 + (L - l)^d

or

A[l] == 2^d A[l + 1] + (L - l)^d

Now we can use RSolve[ ] for our third guess:

Table[(A[l] /. RSolve[#, A[l], l] &@({A[l] == 2^d A[l + 1] + (L - l)^d, A[L] == 0} 
                     /. L -> i) /. l -> 0),
      {i, 2, 7}]
(*
{{-(-1)^d (-HurwitzLerchPhi[2^d, -d, -2] + 2^(2 d) HurwitzLerchPhi[2^d, -d, 0])}, 
 {-(-1)^d (-HurwitzLerchPhi[2^d, -d, -3] + 2^(3 d) HurwitzLerchPhi[2^d, -d, 0])}, 
 {-(-1)^d (-HurwitzLerchPhi[2^d, -d, -4] + 2^(4 d) HurwitzLerchPhi[2^d, -d, 0])}, 
 {-(-1)^d (-HurwitzLerchPhi[2^d, -d, -5] + 2^(5 d) HurwitzLerchPhi[2^d, -d, 0])}, 
 {-(-1)^d (-HurwitzLerchPhi[2^d, -d, -6] + 2^(6 d) HurwitzLerchPhi[2^d, -d, 0])}, 
 {-(-1)^d (-HurwitzLerchPhi[2^d, -d, -7] + 2^(7 d) HurwitzLerchPhi[2^d, -d, 0])}}

*)

So we guess the closed form for the total cost

 A[0] = -(-1)^d (-HurwitzLerchPhi[2^d, -d, -L] + 2^(L d) HurwitzLerchPhi[2^d, -d, 0])

---

Self consistency

Let's see if we arrive at A[L]==0 by using this value for A[0] and the closed form for B[ ]:

B[x_, g_]:= HarmonicNumber[L - x, -g]; 
f[d_, k_]:= Block[{L = k},
            RecurrenceTable[{A[1 + l]== 2^-d (-1 + A[l] -
                                        Sum[B[1 + l,g]*Binomial[d, g], {g, 0, -1 + d}]), 
                             A[0] == -(-1)^d (-HurwitzLerchPhi[2^d, -d, -L] + 
                                      2^(L d) HurwitzLerchPhi[2^d, -d, 0])}, 
                             A, {l, L}]]

Table[Last@f[d, k], {d, 10}, {k, 10}]
(*
 {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, 
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
 *)

So, at least the solution we found is self-consistent!