0

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.

David K
  • 98,388
phandaman
  • 107
  • 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. – dxiv Jul 26 '18 at 00:32

3 Answers3

2

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

Brian Tung
  • 34,160
1

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

Alex R.
  • 32,771
  • 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$? – phandaman Jul 26 '18 at 02:28
  • @phandaman: see the second part with $y_n$. – Alex R. Jul 26 '18 at 06:43
0

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.

Arnaud Mortier
  • 27,276