# 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.

• What you've done with "backwards substitution" can't be done. $a_2$ is defined for $n=2$. You can't then compute $a_3$ with the same $2n-1$ when $n=2$. – Thomas Andrews Apr 4 '13 at 0:06
• – lhf Apr 4 '13 at 0:06
• @ThomasAndrews You are right. I'll fix the post once I finish calculating. – user52272 Apr 4 '13 at 0:21
• Without the $+n$ you have $a_n=(n-1)!$. Do you see that? That is a good place to start – Ross Millikan Apr 4 '13 at 0:59

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*}
• @cRaZiRiCaN, it is just the name of the form of the equation for $x_n$ I give next. The method is just the equations as written. I might be off somewhere, please check each step. – vonbrand Apr 4 '13 at 1:14