1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Thomas Andrews Apr 4 '13 at 0:06
  • $\begingroup$ See oeis.org/A111063 $\endgroup$ – lhf Apr 4 '13 at 0:06
  • $\begingroup$ @ThomasAndrews You are right. I'll fix the post once I finish calculating. $\endgroup$ – user52272 Apr 4 '13 at 0:21
  • $\begingroup$ Without the $+n$ you have $a_n=(n-1)!$. Do you see that? That is a good place to start $\endgroup$ – Ross Millikan Apr 4 '13 at 0:59
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @ThomasAndrews, thanks! Brain malfunction, post fixed (brain presumably still broken). $\endgroup$ – vonbrand Apr 4 '13 at 0:30
  • $\begingroup$ I read this and I definetly lack the knowledge to understand it. Can you include more explanation or specify the methods used? $\endgroup$ – user52272 Apr 4 '13 at 0:42
  • $\begingroup$ @cRaZiRiCaN, please check again. I fixed a few dumb mistakes. $\endgroup$ – vonbrand Apr 4 '13 at 0:48
  • $\begingroup$ @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. $\endgroup$ – vonbrand Apr 4 '13 at 1:14
  • $\begingroup$ 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? $\endgroup$ – user52272 Apr 4 '13 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy