What are the limitations of RecurrenceTable?

Question

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.

Answer 1

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.

Answer 2

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