1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Dohleman Sep 20 '13 at 16:41
  • $\begingroup$ @Dohleman: Thank you. I wasn't questing after their particular method, but just the idea or motivation behind whichever method is best. $\endgroup$ – NNOX Apps Sep 20 '13 at 17:00
4
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – NNOX Apps Sep 20 '13 at 17:06
  • $\begingroup$ Yes that is all that is being done. The recurrence stops when you get to $a_{1}$ for which you have an explicit value $\endgroup$ – Keeran Brabazon Sep 20 '13 at 17:09
  • $\begingroup$ Many thanks. I upvoted. $\endgroup$ – NNOX Apps Sep 21 '13 at 2:59
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ MSE doesn't allow of multiple acceptances, so I upvoted. $\endgroup$ – NNOX Apps Sep 21 '13 at 11:52
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ MSE doesn't allow of multiple acceptances, so I upvoted. $\endgroup$ – NNOX Apps Sep 21 '13 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.