Recurrence Relation Question with a sequence

Question

I have stumbled upon a sequence (0,1,4,15,64...) as the solution to a computer science problem I have been studying. The sequence is known and is given by a(n) = n(a(n-1) + 1), a(0) = 0. My question is whether or not it is appropriate to prove this by induction and how can I re-write this expression to contain factorials so that I can make a proof about its O(n) complexity.

Answer 1

You can easily show (by repeatedly recursing or induction) that for $n\geq 1$ $$a_n=n!\sum_{i=0}^{n-1}\frac 1 {i!}=\lfloor en!\rfloor-1$$