# Using a summation factor to solve a recurrence

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.

• 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 0:32

## 3 Answers

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

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

• 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 2:28
• @phandaman: see the second part with $y_n$. – Alex R. Jul 26 '18 at 6:43

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.