Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

As the title states, I need a solution of this recurrence but I'll provide my own solution and ask if there is an easier, simpler solution using some deeper knowledge about recurrence relations.

$$D_{n} = nD_{n-1} + (n-1)!$$ $$D_{n} = n[(n-1)D_{n-2} + (n-2)!] + n!\frac{1}{n}$$ $$D_{n} = n(n-1)[(n-2)D_{n-3} + (n-3)!] + n!\left(\frac{1}{n} + \frac{1}{n-1}\right)$$ $$\vdots$$ $$D_{n} = n!D_{1} + n!\left(\frac{1}{1} + \ldots + \frac{1}{n}\right)$$ $$D_{n} = n!\left( D_{1} + 1 + \frac{1}{2} + \ldots + \frac{1}{n}\right)$$

Now, my question is, how can one avoid the inductive solution and solve the recurrence with some other tools?

Any books on the subject or areas of mathematics which would make things simpler?

Currently, I only have the knowledge of solving them using Euler's substitution and some other smart tricks which assume the solution has polynomial or exponential form when recurrence is non-homogeneous etc. But!, when factorials are there only thing I can assume is that the solution is of factorial form but that isn't the case here.

share|improve this question
1  
The subject's name of this kind of problems is "(finite) difference equations". A good book about it: "An introduction to difference equations", by Saber Elaydi, Springer UTM. –  a.r. Jan 10 '13 at 7:24

1 Answer 1

up vote 10 down vote accepted

Starting with $D_{n} = nD_{n-1} + (n-1)!$, divide through by $n!$ and let $a_n=\frac{D_n}{n!}$ to get

$$a_n=a_{n-1}+\frac1n\;.$$

Clearly $a_n=H_n+a_0$, where $H_n$ is the $n$-th harmonic number, and $D_n=n!H_n+a_0n!$.

I strongly recommend the book Concrete Mathematics, by R.L. Graham, D.E. Knuth, and O. Patashnik; it contains a great many techniques for dealing with such problems.

share|improve this answer
    
Thanks! The book has been on my to read list for a year now. Went through first two chapters but never finished it. –  Looft Jan 9 '13 at 18:18
2  
@Leolinus: You’re welcome! (And it really is a very good book.) –  Brian M. Scott Jan 9 '13 at 18:20

Your Answer

 
discard

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.