Using a summation factor to solve a recurrence

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.