0
$\begingroup$

On Princeton's Analysis of Algorithms, they discuss solving recurrence relations and they come across a line that I can't seem to decipher

\begin{align} n(n-1)a_n &=(n-1)(n-2)a_{n-1} + 2(n-1)\\ &=(n-2)(n-3)a_{n-2}+2(n-2)+2(n-1)\\ &=2(1+2+\cdots+n-1)\\ &=n(n-1)\\ a_n&=1 \end{align}

Basically lines (1) through (4) I am not sure how they are making those simplifications. If it's a matter of reading up on some literature a reference would be greatly appreciated.

$\endgroup$
  • $\begingroup$ It's easier to follow if you first define $\,b_\color{red}{n} = \color{red}{n}(\color{red}{n}-1)a_{\color{red}n-1}\,$. Then changing $\,n \mapsto n-1\,$ gives $\,b_\color{red}{n-1} = \color{red}{(n-1)}(\color{red}{n-1}-1)a_{\color{red}{n-1}-1}$ $=(n-1)(n-2)a_{n-2}\,$, so the recurrence can be written as $\,b_n = b_{n-1}+2(n-1)\,$, then it telescopes from there on. $\endgroup$ – dxiv Jul 26 '18 at 0:32
2
$\begingroup$

$$ n(n-1)a_n = (n-1)(n-2)a_{n-1}+2(n-1) $$

Let $m = n-1$, then $(n-1)(n-2)a_{n-1} = m(m-1)a_m$. From this, we can apply the recurrence again.

$$ n(n-1)a_n = [(m-1)(m-2)a_{m-1}+2(m-1)]+2(n-1) $$

Then let $k = m-1$, then $(m-1)(m-2)a_{m-1} = k(k-1)a_k$. We apply the recurrence again.

$$ n(n-1)a_n = \left[[(k-1)(k-2)a_{k-1}+2(k-1)]+2(m-1)\right]+2(n-1) $$

And so on. Each time, we add another constant term on the right: first $2(n-1)$, then $2(m-1) = 2(n-2)$, then $2(k-1) = 2(n-3)$. This continues until we run out of positive terms.

$\endgroup$
1
$\begingroup$

The equality in line (2) just plugs in the definition of (1) back into the r.h.s. E.g. $(n-1)(n-2)a_{n-1} = (n-2)(n-3)a_{n-2}+2(n-2)$.

The equality in line (3) comes from repeated use of (1). E.g:

$n(n-1)a_n = (n-k)(n-k+1)a_{n-k} + \sum_{i=1}^k 2(n-i)$.

Can you take it from here?

If it helps, define $y_n:=n(n-1)a_n$. Then the recursion is rewritten to be $y_n=y_{n-1}+2(n-1)$. Then $y_{n}-y_{n-1}=2(n-1)$. Now sum both sides from $n=1$ to $n$. The left side will telescope.

Once you solve for $y_n$, you can then solve for $a_n$.

$\endgroup$
  • $\begingroup$ I see that you are plugging in the recurrence relationship between lines 1 and 2 and lines 3 to 4 is basically the sum of the first $n$ integers with a factor of 2. The step in between 2 and 3 is still elusive. How does applying the recurrence relation many times get rid of the $a_{n-k}$ dependence and give you a sum from $n=1$ to $n-1$? $\endgroup$ – phandaman Jul 26 '18 at 2:28
  • $\begingroup$ @phandaman: see the second part with $y_n$. $\endgroup$ – Alex R. Jul 26 '18 at 6:43
0
$\begingroup$

What this means is that if the first line is true for all $n$, then by induction you can prove that $n(n-1)a_n=n(n-1)$ and derive that $a_n=1$ for all $n$.

Implicitly the assumption $a_1=1$ must have been made somewhere above in the text.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.