Solution 2.4.3.1.

To get a feel for the recurrence relation, write out the first few terms of the sequence: \(4, 5, 7, 10, 14, 19, \ldots\text{.}\) Look at the difference between terms. \(a_1 - a_0 = 1\) and \(a_2 - a_1 = 2\) and so on. The key thing here is that the difference between terms is \(n\text{.}\) We can write this explicitly: \(a_n - a_{n-1} = n\text{.}\) Of course, we could have arrived at this conclusion directly from the recurrence relation by subtracting \(a_{n-1}\) from both sides.

Now use this equation over and over again, changing \(n\) each time:

\begin{align*} a_1 - a_0 \amp = 1\\ a_2 - a_1 \amp = 2\\ a_3 - a_2 \amp = 3\\ \vdots \quad \amp \quad \vdots\\ a_n - a_{n-1} \amp = n\text{.} \end{align*}

Add all these equations together. On the right-hand side, we get the sum \(1 + 2 + 3 + \cdots + n\text{.}\) We already know this can be simplified to \(\frac{n(n+1)}{2}\text{.}\) What happens on the left-hand side? We get

\begin{equation*} (a_1 - a_0) + (a_2 - a_1) + (a_3 - a_2) + \cdots (a_{n-1} - a_{n-2})+ (a_n - a_{n-1})\text{.} \end{equation*}

This sum telescopes. We are left with only the \(-a_0\) from the first equation and the \(a_n\) from the last equation. Putting this all together we have \(-a_0 + a_n = \frac{n(n+1)}{2}\) or \(a_n = \frac{n(n+1)}{2} + a_0\text{.}\) But we know that \(a_0 = 4\text{.}\) So the solution to the recurrence relation, subject to the initial condition is

\begin{equation*} a_n = \frac{n(n+1)}{2} + 4\text{.} \end{equation*}

(Now that we know that, we should notice that the sequence is the result of adding 4 to each of the triangular numbers.)