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, 2013 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, 2013 at 17:00

4 Answers 4

5
$\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, 2013 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$ Sep 20, 2013 at 17:09
  • $\begingroup$ Many thanks. I upvoted. $\endgroup$
    – NNOX Apps
    Sep 21, 2013 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, 2013 at 11:52
2
$\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, 2013 at 3:01
1
$\begingroup$

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

$\endgroup$

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.