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

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.

• From your initial conditions I get a[1, 1]=1; how would I calculate a[1,2] = a[1, 1]+a[0,1] + a[0, 2] ? – b.gates.you.know.what Jun 22 '15 at 9:10
• @b.gatessucks a[1, 2] = 1 according to the initial condition a[1,n] == 1. No need to apply the recurrence for it. – hengxin Jun 22 '15 at 10:20

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}]

• thank you for this instructive answer +1 :) – ubpdqn Jun 22 '15 at 20:32

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]: