1

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.

1 Answers1

1

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

vonbrand
  • 27,812
  • @ThomasAndrews, thanks! Brain malfunction, post fixed (brain presumably still broken). – vonbrand Apr 04 '13 at 00:30
  • I read this and I definetly lack the knowledge to understand it. Can you include more explanation or specify the methods used? –  Apr 04 '13 at 00:42
  • @cRaZiRiCaN, please check again. I fixed a few dumb mistakes. – vonbrand Apr 04 '13 at 00:48
  • @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 04 '13 at 01:14
  • Whats the reasoning for dividing by the u terms? Does the notation of the u terms mean they are multiplied by each other? After dividing by the u terms how did you get the next equation? –  Apr 04 '13 at 02:45
  • @cRaZiRiCaN, $u_n \ldots u_0 = \prod_{0 \le k \le n} u_k$; by dividing you get terms that telescope when adding up. The very first term is $\dfrac{x_1}{u_0} -\dfrac{u_0 x_0}{u_0} = \dfrac{x_1}{u_0} - x_0$, then $\dfrac{x_2}{u_1 u_0} - \dfrac{u_1 x_1}{u_1 u_0} = \dfrac{x_2}{u_1 u_0} - \dfrac{x_1}{u_0}$, and so on. – vonbrand Apr 04 '13 at 09:50