<s>[INST] Stuck finding a recursive recurrence relation. I am analyzing the following algorithm:
QUANT(n):
 if n == 0 or n == 1:
  return 1
 else
  return (n-1)*QUANT(n-1) + n

I need to find the recurrence relation of this algorithm and prove it using mathematical induction. Here is what I have tried so far:
$$a_0 = 1, a_1 = 1, a_n = (n-1)*a_{n-1} + n$$
$$a_0 = 1$$
$$a_1 = 1$$
$$a_2 = 1 + 2 = 3$$
$$a_3 = (2)(3) + 3 = 9$$
$$a_4 = (3)(9) + 4 = 31$$
$$a_5 = (4)(31) + 5 = 129$$
Also tried backwards substitution:
$$a_0 = 1$$
$$a_1 = 1$$
$$a_2 = (n-1) + n = 2n - 1$$
$$a_3 = (n-1)(2(n-1)-1) + n = 2n^2 -4n + 3$$
$$a_4 = (n-1)(2(n-1)^2-2(n-1)+1)+n=2n^3-10n^2+10n-1$$
$$a_5 = (n-1)(2(n-1)^3-4(n-1)^2+4(n-1)-1)+n=2n^4-18n^3+52n^2-58n+23$$
I am having trouble finding a pattern. For the backwards one I can detect some things like the first term is always $2n^{n-1}$, all the powers of $n$ are expressed. Please point out what concept of series I am missing to find the pattern, if there is one.
 [/INST] You have the recurrence:
$$
a_{n + 1} = n a_n + n + 1 \quad a_0 = 1
$$
This is a non-homogeneous linear first order recurrence. If you have:
$$
x_{n + 1} - u_n x_n = f_n
$$
Dividing by $u_n \ldots u_0$ gives:
$$
\frac{x_{n + 1}}{u_n \ldots u_0} - \frac{x_n}{u_{n - 1} \ldots u_0} 
   = \frac{f_n}{u_n \ldots u_0}
$$
This is easy to sum:
$$
\frac{x_n}{u_{n - 1} \ldots u_0} = x_0
                    + \sum_{0 \le k \le n - 1} \frac{f_k}{u_k \ldots u_0}
$$
In our case $u_n = n$, $f_n = n + 1$. To avoid division by 0, better start at index 1. Then:
$$
\begin{align*}
\frac{a_n}{(n - 1)!} &= \frac{a_1}{0!} 
                   + \sum_{1 \le k \le n - 1} \frac{k + 1}{(k + 1)!} \\
a_n           &= (n - 1)! + (n - 1)! \sum_{1 \le k \le n - 1} \frac{1}{k!} \\
              &= (n - 1)! \sum_{0 \le k \le n - 1} \frac{1}{k!}
\end{align*}
$$
</s>