Evaluating a Recursive Expression

Question

Why does this raise an error

P[0, x_] := 1

P[1, x_] := x

P[n_, x_] := ((2 n - 1)/n)*x*P[n - 1, x] - ((n - 1)/n)*P[n - 2, x]

Simplify[P[n, x]] /. n -> 2

(*$RecursionLimit::reclim: Recursion depth of 256 exceeded. >>*)

But this does not

P[0, x_] := 1

P[1, x_] := x

P[n_, x_] := ((2 n - 1)/n)*x*P[n - 1, x] - ((n - 1)/n)*P[n - 2, x]

Simplify[P[2, x]] 

1/2 (-1 + 3 x^2)

More generally how does one generate a list of 1000 polynomials from this recursion? All of the following still seem to raise errors.

Unevaluated@P[n, x] /. n -> {2, 3}

Simplify[Unevaluated@P[n, x] /. n -> {2, 3}]

Simplify[Unevaluated@P[n, x]] /. n -> {2, 3}

{Unevaluated@P[n, x] /. n -> z} /. z -> {2, 3}

If my questions indicate that I am not familiar with mathematica, it is because I am not. :-)

Answer 1

A simpler example where I tell Mathematica to print what it's doing. I ClearAll[n] to make sure n has no value set.

ClearAll[n];
f[0] = 0
f[n_] := f[n - 1]
Block[{$RecursionLimit = 20, $IterationLimit = 20},
 TracePrint[f[n]]
 ]

See that there is a bunch of f[-10+n] etc, but since n is not assigned any value -10+n is not zero, and neither is -12+n or anything else of the sort.

This means that f[0] will never get matched, i.e. it will go on forever, this is a bad thing and you don't want that to happen, for that reason there are global variables $RecursionLimit and $IterationLimit that make sure this doesn't happen. If for some reason you don't want a limit you can set them to Infinity in this case that could crash Mathematica and possibly your computer

Answer 2

The pattern on the right hand side P[n_, x_] matches the new expressions created on the left hand side, namely P[n - 1, x] and P[n - 2, x] leading to infinite recursion when n is a symbol. When you use a concrete value, i.e. n = 2, then it actually uses the end cases, eventually, if the initial n > 0.

Therefore, in the expression Simplify[P[n, x]] /. n -> 2, Mathematica first attempts to resolve P[n, x] through the rules you provide, failing into the issue mentioned above.

The second expression Simplify[P[2, x]] does not have this issue as explained.

To address your intention, you need to use a procedure that holds P[n,x] unevaluated. For example, Table just does that so this works

p[0, x_] := 1;
p[1, x_] := x;
p[n_, x_] := ((2 n - 1)/n) x p[n - 1, x] - ((n - 1)/n) p[n - 2, x];
Table[Simplify[p[n, x]], {n, 10}]

I used lowercase p as it is best practice to use lowercase for user defined symbols, and you don't need the explicit * either. Hope this helps.