# RecurrenceTable not evaluated: mathematica just echoes input

Forgive the newbie question... I am trying to create a table of the following system, following the Stirling example in the documentation, but Mathematica just echoes my input. What am I doing wrong?

RecurrenceTable[
{s1[n, k] == s1[n, k - 1] + s1[n - 1, k - 1],
s1[0, k] == 1, s1[n, 0] == Boole[n == 0], s1[n, 1] == Boole[n <= 2]},
s1, {n, 0, 6}, {k, 0, 4}
] // Grid

-

As far as I can see with a quick look, you system is overdetermined.
You have to leave out s1[0, k] == 1

RecurrenceTable[
{
s1[n, k] == s1[-1 + n, -1 + k] + s1[n, -1 + k],
s1[n, 0] == Boole[n == 0],
s1[n, 1] == Boole[n <= 2]
}, s1, {n, 0, 6}, {k, 0, 4}] // Grid

(*
1   1   1   1   1
0   1   2   3   4
0   0   1   3   6
0   0   0   1   4
0   0   0   0   1
0   0   0   0   0
0   0   0   0   0
*)

-
Interesting, so coding explicitly does not pick up overdetermination, whereas RecurrenceTable detects it? –  mitchus Feb 16 '12 at 15:27
Isn't it a good thing, that RecurrenceTable points out that something is wrong? With function definitions as acl suggested it's brought down to pattern matching which simply gives wrong results if you made a mistake. I don't know how powerful the error detection of RecurrenceTable is, but leaving the expression unevaluated is often used for I do not know what to do in Mathematica. –  halirutan Feb 16 '12 at 15:43
yes, that is a good point. –  acl Feb 16 '12 at 15:48
Yes true. It would be even better if Mathematica gave a clue as to why it can't do anything. Is there a way to make it more "verbose" in such cases? –  mitchus Feb 16 '12 at 16:16

There is an available-on-request package Guess.m that can solve some recurrence relations that Mathematica natively cannot. I suggest you give it a try if you do this kind of thing often.

-
Interesting, I will give it a spin. –  mitchus Feb 16 '12 at 15:23

You are not doing anything wrong. Mathematica is attempting to solve the recurrence equations and, apparently, failing.

If what you want is to construct the table, you can do so by explicitly coding the recursive definition as follows (this is inefficient, and one can speed it up in any of several different ways):

ClearAll[s1];
s1[0, k_] := 1;
s1[n_, 0] := Boole[n \[Equal] 0];
s1[n_, 1] := Boole[n \[LessEqual] 2];
s1[n_, k_] := s1[n, k] = s1[n - 1, k - 1] + s1[n, k - 1]


(I hope I did not transcribe anything wrong). Notice the memoization in the last line which speeds things up quite a bit, as well as preventing recursion from getting too deep.

The table is then easy to produce:

Table[s1[n, k], {n, 0, 6}, {k, 0, 4}] // Grid


(I have no idea if this is correct; if not, I have transcribed the definition incorrectly).

In summary, one must make a distinction between explicitly evaluating the recurrence relations (as I do here) and attempting to "solve" the recurrence relations. This distinction is similar to that between Total@Table[f[i],{i,1,10}] (which produces a bunch of numbers, if f is defined, and then adds them up), and Sum[f[i],{i,1,10}], which attempts to perform a much more sophisticated operation. Another way to view this is as a distinction between mathematics and programming; mathematically, one is just producing a table of these values defined by a recurrence relation; but in terms of what is going on, RecurrenceTable is apparently trying to do something rather sophisticate (and, it seems, failing), while what I do is carrying out the definition of the recurrence literally and with specific numbers until it bottoms out.

-
s1[0,k]==1 for k==0 or s1[n, 0] == Boole[n == 0] is 1 for n==0 and therefore your first entry is wrong. –  halirutan Feb 16 '12 at 14:03
@halirutan Right, thanks. Fixed it (I think!) –  acl Feb 16 '12 at 14:08
I actually prefer your explicit method over the RecurrenceTable, it seems to allow greater control. It also has more pitfalls though, apparently :) –  mitchus Feb 16 '12 at 15:29