# Closed form of two-layer recurrence

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. >>  • Sorry ... What expression is the "total cost"? – Dr. belisarius Jun 9 '15 at 17:40 • @belisarius Pardon, I can see this was unclear. The quantity I am interested in expressing is essentially$A(0)$(or$A(L)$if the$\ell\$ counter is decremented instead of incremented in the recurrence forms). I have edited my question accordingly. – Sweeters Jun 9 '15 at 17:50
• Also, I believe that you mean that the termination condition for B is B[L+1,_]==0 because you don't want the total cost in terms of g – Dr. belisarius Jun 9 '15 at 17:56
• @belisarius That is correct. (I was not aware of this syntax.) I have again edited the posted question to reflect this, and added an alternative solution approach. – Sweeters Jun 9 '15 at 18:11

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!

• Many thanks for the detailed walk through your approach! It has been very informative, and in fact helped me to find and fix an error with my formulas. I have managed to empirically verify the solution I was expecting for the corrected problem, but cannot seem to get a closed-form solution, still. I feel I should accept your answer, however, rather than try to start another round of iterations over a similar question... I am not sure if this is appropriate SE etiquette, so please let me know what you'd rather have me do. – Sweeters Jun 14 '15 at 17:43