Why does Mathematica not evaluate the difference recurrence using `RSolve` or `RecurrenceTable`?

Question

Mathematica does not evaluate the following recurrence of two variables using RSolve and only echoes the input:

RSolve[{a[m, n] == a[m, n - 1] + a[m - 1, n - 1] + a[m - 1, n], a[1, n] == 1, a[m, 1] == 1}, a[m, n], {m, n}]

Then, I settle for RecurrenceTable, and Mathematica does not evaluate it either:

RecurrenceTable[{a[m, n] == a[m, n - 1] + a[m - 1, n - 1] + a[m - 1, n], a[1, n] == 1, a[m, 1] == 1}, a, {m, 1, 3}, {n, 1, 3}] // Grid

Problem: Why does Mathematica not evaluate the recurrence? Maybe Mathematica cannot find the closed form for it using RSolve, but why does it not evaluate the recurrence using RecurrenceTable either?

---

My Trials:

If I remove the a[m, n - 1] part from the recurrence, it works:

RecurrenceTable[{a[m, n] == a[m - 1, n - 1] + a[m - 1, n], a[1, n] == 1, a[m, 1] == 1}, a, {m, 1, 3}, {n, 1, 3}] // Grid
(*
   1 1 1
   2 2 2
   4 4 4
*)

If I leave a[m, n - 1] and remove any one (or both) of the other two parts from the recurrence, it does not work again.

---

In document for RecurrenceTable, there is a similar example:

RecurrenceTable[{s1[n, k] == s1[n - 1, k - 1] - (n - 1) s1[n - 1, k], s1[0, k] == KroneckerDelta[k]}, s1, {n, 0, 6}, {k, 0, 4}] // Grid

So, I just guess that it may be required for the first parameter to be decreased in the recurrence.

---

Similar Post: This post comes up with the same problem, but it asks for additional ways instead of what is going on here.

Answer 1

Although this is not an answer to the question as put, the problem can be solved completely with Mathematica as follows. This is also a hint to try alternative formulations in mathematica if a specific one does not succeed. Assuming, of course, that the problem is in the center of interest.

The easiest way to obtain the values of a[n,m] is to start with these equations which are just your recurrence relations written as function definitions:

a[n_, m_] := a[n, m] = a[n - 1, m] + a[n - 1, m - 1] + a[n, m - 1]

a[1, m_] := a[1, m] = 1

a[n_, 1] := a[n, 1] = 1

The first few a[n,m] are then

nn = 10;
t = Table[a[n, m], {n, 1, nn}, {m, 1, nn}]

(*
Out[104]= {
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 
{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}, 
{1, 5, 13, 25, 41, 61, 85, 113, 145, 181}, 
{1, 7, 25, 63, 129, 231, 377, 575, 833, 1159}, 
{1, 9, 41, 129, 321, 681, 1289, 2241, 3649, 5641}, 
{1, 11, 61, 231, 681, 1683, 3653, 7183, 13073, 22363}, 
{1, 13, 85, 377, 1289, 3653, 8989, 19825, 40081, 75517}, 
{1, 15, 113, 575, 2241, 7183, 19825, 48639, 108545, 224143}, 
{1, 17, 145, 833, 3649, 13073, 40081, 108545, 265729, 598417}, 
{1, 19, 181, 1159, 5641, 22363, 75517, 224143, 598417, 1462563}}
*)

Now it is easy to show that the generating function is related to

g[x_, y_] := 1/(1 - (x + y  + x y))

in fact the series coefficients (shiften by 1) of g given by

b[n_, m_] := 
 1/((m - 1)! (n - 1)!) D[g[x, y], {x, n - 1}, {y, m - 1}] /. {x -> 0, 
   y -> 0}

are identical to a[n,m].

Expanding the series g using the binomial theorem twice we find an explicit formula for a[n,m] in the form

c[n_, m_] := 
 Sum[Binomial[k, 2 k - n - m + 2] Binomial[2 k - n - m + 2, k - m + 1], {k, 
   0, \[Infinity]}]

It takes some time to evaluate but it is an expilcit formula.

EDIT #1

The formulas starting from the generating function can be simplified. The new names have a number 1 appended.

Generating function

g1[x_, y_] := x y /(1 - (x + y  + x y))

Coefficients of series expansion (no shift anymore)

b1[n_, m_] := 
 1/(m! n!) D[g1[x, y], {x, n}, {y, m}] /. {x -> 0, y -> 0}

Explicit formula of solution (now an explicitly finite sum)

c1[n_, m_] := 
 Sum[Binomial[k - 1, 2 k - m - n] Binomial[2 k - m - n, k - m], {k, 
   Min[n, m], n + m - 1}]

or, symmetrically, and with explicit visibility of the limits of summation due to 1/r! = 0 if r<0

c2[n_, m_] := 
 Sum[(k - 1)!/((n + m - 1 - k)! (n - k)! (m - k)!), {k, Min[n, m], 
   n + m - 1}]

Answer 2

I will not answer the failure of in-built functions but present an alternative approach:

f[m_, u_] := With[{r = {{-1, 0}, {0, -1}, {-1, -1}}},
   ReplacePart[m, u -> Total[(Extract[m, u + #1] &) /@ r]]];
sa[m_, n_] := Module[{s, p},
   s = Normal@SparseArray[{{i_, 1} -> 1, {1, j_} -> 1}, {m, n}, "x"];
   p = Position[s, "x"];
   Fold[f[#1, #2] &, s, p]];
vis[m_, n_] := 
  TableForm[sa[m, n], TableHeadings -> {Range[m], Range[n]}];

For example, vis[10,8]: