# Using RSolve correctly

I am having problems persuading Mathematica to solve even the simplest recurrence relations. As an example, how would you do the following?

RSolve[{q[i] == 1 + (i - 1)*q[i - 1], q[0] == 0}, q[i], {i}]


Addendum. As a further frustration, isn't this exactly equivalent? Mathematica can't solve it it seems.

RSolve[{q[i, k] == 1 + ((i - 1))*q[i - 1, k - 1], q[1, 1] == 1},
q[i, k], {i, k}]

-
I think it's the initial condition. Remove it and try again. If you notice from the recursion eq. the value of $q$ at $0$ doesn't matter. –  Spawn1701D Apr 20 '13 at 7:43
If you run your code, the returned error ("...the given boundary conditions lead to an empty solution.") is pretty helpful. –  István Zachar Apr 20 '13 at 7:48
If you want to use an initial condition use the natural one, q[1]==1. –  Spawn1701D Apr 20 '13 at 7:51
That seems very unhelpful of Mathematica to me. q[1]==1 gives a useful answer. How would you know which initial conditions it will be happy with? –  Anush Apr 20 '13 at 7:54
@Anush if the result when using q[1] == 1 is what you want, E Gamma[i, 1], you should note that E Gamma[i, 1] with i = 0 is ~= 0.596347, not zero. Or do you want something else? –  Mr.Wizard Apr 20 '13 at 8:40
show 1 more comment

The incomplete Euler gamma function is defined with :

$$\Gamma(a,z)=\int_{z}^{\infty} t^{a-1} e^{-t} d t$$

You can observe that the integral is defined for Re[a] > 0 :

Integrate[t^(a - 1) Exp[-t], {t, 0, Infinity}]

ConditionalExpression[ Gamma[a], Re[a] > 0]


while for a == 0 this does not converge.

Starting with your recurrence relation one easily finds : $q(1)=1,\; q(2)=2,\; q(3) = 5,\; q(4)=16$.

Taking the initial condition $q(1)=1\;$ instead of $q(0)=0\;$ we find :

RSolve[{ q[n] == 1 + (n - 1) q[n - 1], q[1] == 1}, q[n], n]

 {{q[n] -> E Gamma[n, 1]}}


This is correct since we can simplfy it with FullSimplify, even though one cannot simplify the original result E Gamma[n, 1] directly for all natural numbers.

FullSimplify[ Table[E Gamma[n, 1], {n, 8}], n ∈ Range[8]]

{1, 2, 5, 16, 65, 326, 1957, 13700}


Another recurrence relation is clearly not equivalent to the original one. That relation binds values for equal k and i only, not for all natural i and k like you seem to expect. RSolve perhaps will be updated with more options in the future but they should be appropriate to satisfy only perfectly well posed conditions.

You can see that your original initial condition (for i == 0) has been inappropriate to satisfy the final result in terms of the Euler gamma function.

-
Thank you. You are quite right about the addendum (and I was wrong). I needed to have a way to specify that $i=k$. In terms of the initial condition $i==0$ although I see your point I don't think I agree. A perfectly good answer would be if $n \geq 1$ then $q[n]= e$ Gamma$[n,1]$, if $n =0$ then $q[n]=0$ wouldn't it? –  Anush Apr 20 '13 at 13:25
@Anush Mathematica is 25 years old, while RSolve only 10, you shouldn't expect perfect answers so far. Nevertheless this function is quite good. Another point is that any software system cannot be free of inconsistencies. –  Artes Apr 20 '13 at 13:52
Of course. Maybe it would be nice to have a central wiki for these feature requests/bugs. –  Anush Apr 20 '13 at 16:28

q[0] = 0 q[i_] := 1 + (i - 1)*q [i - 1]

And I used the following code to find some terms for the above sequence.

For[k = 1, k < 12, k++, Print[ q [ k ] ] ]. And the output is

1, 2, 5, 16, 65, 326, 1957, 13700, 109601, 986410, 9864101

These numbers are "Total number of arrangements of a set with n elements". You can find them here.

-
RecurrenceTable would be a good way to get the list of values: RecurrenceTable[{q[n] == 1 + (n - 1) q[n - 1], q[0] == 0}, q, {n, 1, 10}] –  Simon Woods Apr 20 '13 at 11:43