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.
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*} $$