# What are the limitations of RecurrenceTable?

Background

Consider a recurrence relationship defined in terms of the following recursive functions (which works correctly):

Clear[tt];
tt[p_][0, j_] := 1
tt[p_][i_, 0] := 0

tt[p_][i_, j_] := p*tt[p][i - 1, j] + (1 - p)*tt[p][i, j - 1]

tt[0.3][11, 11] (* usage example *)


Question:

What's the proper way to evaluate this using the build-in RecurrenceTable functionality? Or stated another way---is there some limitation in the functional forms that RecurrentTable works with that prevents evaluating these types of functions?

For example, the following implementation:

Clear[tt, i, j, p]
p = 0.3;
RecurrenceTable[
{tt[i, j] == p*tt[i - 1, j] + (1 - p)*tt[i, j - 1],
tt[0, j] == 0,
tt[i, 0] == 1},
tt,
{i, 11}, {j, 11}]


only returns the (unevaluated input-form-style output): RecurrenceTable[{tt[i, j] == 0.3 tt[-1 + i, j] + 0.7 tt[i, -1 + j], tt[0, j] == 0, tt[i, 0] == 1}, tt, {i, 11}, {j, 11}] instead of providing the numerical output.

What is puzzling is that the RecurrenceTable documentation includes an example for the Stirling numbers of the first kind which has a very similar form (and works just fine):

Clear[s1, k] (*example from documentation which works fine*)
RecurrenceTable[
{s1[n, k] == s1[n - 1, k - 1] - (n - 1) s1[n - 1, k],
s1[0, k] == KroneckerDelta[k]},
s1,
{n, 6}, {k, 4}]


Unlike past Q&A's, this is not a case where there is a constant right hand side. Previous questions have posed similar types of problems where a RecurrenceTable does not evaluate, but the same set of equations restated as a set of recursive functions works fine (example 1, example 2). Those past answers have all offered the solution, but I'm interested in why RecurrenceTable is limited in this way.

As an educated guess, in the Stirling number example, the recurrence depending on $$n-1$$ is key. Mathematica expects that. What you are attempting depends on both $$i-1$$ and $$i$$. The documentation does not make this clear. However, it is still possible to use RecurrenceTable within its limitation. Using the usual recurrence technique is this code

ClearAll[tt, p, q];
tt[i_ /; i <= 0, _] = 0;
tt[i_, 0] := Boole[i > 0];
tt[i_ /; i > 0, j_ /; j > 0] := tt[i, j] =
p*tt[i - 1, j] + q*tt[i, j - 1] // Expand;
Table[tt[n - j, j], {n, 0, 4}, {j, 0, 3}] // InputForm


which evaluates to

{{0, 0, 0, 0}, {1, 0, 0, 0}, {1, q, 0, 0}, {1, q + p*q, q^2, 0},
{1, q + p*q + p^2*q, q^2 + 2*p*q^2, q^3}}


The equivalent code using RecurrenceTable is this

ClearAll[tt, p, q];
RecurrenceTable[{tt[n, j] == If[j == 0, 1,
p*tt[n - 1, j] + q*tt[n - 1, j - 1] // Expand],
tt[0, j] == 0}, tt, {n, 0, 4}, {j, 0, 3}] // InputForm


which evaluates to the same thing.

I do not know why RecurrenceTable does not work. But you can easily do it "by hand". For an example, I only calculate i,j up to 6:

ClearAll[tt]
tt[0, j_?NumericQ] = 0;
tt[i_?NumericQ, 0] = 1;
tt[i_?NumericQ, j_?NumericQ] = p*tt[i - 1, j] + (1 - p)*tt[i, j - 1];
Table[tt[i, j], {i, 0, 6}, {j, 0, 6}] // MatrixForm • Right. As noted above, my question is more about the "why it doesn't work aspect". Jun 2, 2021 at 14:43