# Explicit Formula for a Recurrence Relation for {2, 5, 9, 14, ...} (Chartrand Ex 6.46[b])

Consider the sequence $a_1 = 2, a_2 = 5, a_3 = 9, a_4 = 14,$ etc...
(a) The recurrence relation is: $a_1 = 2$ and $a_n = a_{n - 1} + (n + 1) \; \forall \;n \in [\mathbb{Z \geq 2}]$.
(b) Conjecture an explicit formula for $a_n$. (Proof for conjecture pretermitted here)

I wrote out some $a_n$ to compass to cotton on to an idea or pattern. It seems bootless.

$\begin{array}{cc} a_2 = 5 & a_3 = 9 & a_4 = 14 & a_5 = 20 & a_6 = 27\\ \hline \\ 5 = 2 + (2 + 1) & 9 = 5 + (3 + 1) & 14 = 9 + (4 + 1) & 20 = 14 + (5 + 1) & 27 = 20 + (7 + 1) \\ \end{array}$

The snippy answer only says $a_n = (n^2 + 3n)/2$. Thus, could someone please explicate the (missing) motivation or steps towards this conjecture? How and why would one envision this?

• They could have arrived at that conjecture any number of ways. Are you asking for their particular method? I'm not sure we can determine that. Sep 20, 2013 at 16:41
• @Dohleman: Thank you. I wasn't questing after their particular method, but just the idea or motivation behind whichever method is best. Sep 20, 2013 at 17:00

Write out the series for $a_{n}$ to start with. We have that

$a_{n} = a_{n-1} + (n+1)\\ \quad = a_{n-2} + n + (n+1) \\ \quad = \ldots \\ \quad = a_{1} + 3 + 4 + \ldots + (n+1) \\ \quad = 2 + 3 + 4 + \ldots + (n+1) \\ \quad = \displaystyle \left(\sum_{i=1}^{n+1} i \right) - 1 \\ \quad = (n+1)(n+2)/2 - 1, \quad (\text{using the value for the sum of the integers between 1 and}\ n + 1) \\ \quad = (n^{2} + 3n)/2 + 1 -1 \\ \quad = (n^{2} + 3n)/2$

• Thank you! What are the critical ideas behind your calculations? Anything more than the substitution of the recurrence relation $a_n$ repeatedly until it disappears and unravels, at which point you recover $a_1$? I ask since I didn't perceive it. Sep 20, 2013 at 17:06
• Yes that is all that is being done. The recurrence stops when you get to $a_{1}$ for which you have an explicit value Sep 20, 2013 at 17:09
• Many thanks. I upvoted. Sep 21, 2013 at 2:59

$a_n$ is equal to $2 + 3 + \ldots + (n+1)$. You can apply reasoning to $a_n$ by taking two copies of $a_n$, one with sum of terms in forward direction, and one with sum of terms in reverse direction, and you will get $n$ pairs of terms each of which add up to $n+3$. So $2a_n = n(n+3)$.

• MSE doesn't allow of multiple acceptances, so I upvoted. Sep 21, 2013 at 11:52

Let $2\leq n$, then you can write $$a_{2}-a_{1}=2+1$$ $$a_{3}-a_{2}=3+1$$ $$...$$ $$a_{n}-a_{n-1}=n+1.$$ Now addition of all this equality implies that $$a_{n}-a_{1}=(2+3+..+n)+(n-1),$$ $$a_{n}=(2+3+..+n)+(n+1)-1,$$ we know that $1+2+..+n=\frac{n^{2}+n}{2}$, so $$a_{n}=\frac{(n+1)(n+2)}{2}-1$$

• MSE doesn't allow of multiple acceptances, so I upvoted. Sep 21, 2013 at 3:01

Hint: $a_n=a_{n-1}+(n+1)=a_{n-2}+n+(n+1)=\ldots=a_1+3+\ldots+(n+1)$.