Solving or approximating recurrence relations for sequences of numbers
Converting Full History to Limited History

This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers.  Consider, for example, the recurrence
$$
T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big)
$$
which arises in the analysis of randomized quicksort.  (Here, $k$ is the rank of the randomly chosen pivot.)  For any integer $n$, the value of $T(n)$ depends on all $T(k)$ with $k&lt;n$.  Recurrences of this form are called full history recurrences.

To solve this recurrence, we can transform it into a limited history recurrence, where $T(n)$ depends on only a constant number of previous values.  But first, it helps to simplify the recurrence a bit, to collect common terms and eliminate pesky fractions.
\begin{align*}
n T(n) &amp;= n^2 + 2\sum_{k=1}^{n-1} T(k)
\end{align*}
Now to convert to a limited-history recurrence, we write down the recurrence for $T(n-1)$, subtract, and regather terms:
\begin{align*}
(n-1) T(n-1) &amp;= (n-1)^2 + 2\sum_{k=1}^{n-2} T(k)
\\
\implies 
nT(n) - (n-1)T(n-1) &amp;= (2n-1) + 2T(n-1)
\\[1ex]
\implies 
n T(n) &amp;= (2n-1) + (n+1) T(n-1)
\\[1ex]
\implies 
\frac{T(n)}{n+1} &amp;= \frac{2n-1}{n(n+1)} + \frac{T(n-1)}{n}
\end{align*}

Now if we define $t(n) = T(n)/(n+1)$ and replace the fraction $\frac{2n-1}{n(n+1)}$ with the simpler asymptotic form $\Theta(1/n)$, we obtain the much simpler recurrence
$$
t(n) = \Theta(1/n) + t(n-1).
$$
Expanding this recurrence into a summation immediately gives us $t(n) = \Theta(H_n) = \Theta(\log n)$, where $H_n$ is the $n$th harmonic number.  We conclude that $\boldsymbol{T(n) = \Theta(n\log n)}$.