Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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
up vote 8 down vote accepted

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}

Ad addendum

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.

share|improve this answer
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

Your sequence is

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.

share|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.