Given sequence:

$A_1 = 0$ $A_2 = 1$ $A_3 = 3$ $A_4 = 6$ $A_5 = 10$ ...

And the recursive formula is given as $A_n = A_{n-1} + (n - 1)$

How can one find this sequence's explicit formula?


Hint. One may write $$ A_n - A_{n-1} = (n - 1),\qquad n\ge2, $$ then summing from $2$ to $N$ terms telescope on the left hand side getting $$ A_N - A_1 = \sum_{n=2}^N(n - 1)=\frac{N(N-1)}2. $$


We recognise $0,1,3,6,10,\cdots$ as $\displaystyle \left[\binom 12\right], \binom 22, \binom 32,\binom42, \binom 52,\cdots $ and conjecture that $$\color{red}{A_n=\binom n2}$$ Testing this in the recurrence relation given: $$A_n-A_{n-1}=\binom n2-\binom {n-1}2=\frac {n(n-1)}2-\frac {(n-1)(n-2)}2=n-1\\ \Longrightarrow A_n=A_{n-1}+(n-1)$$ Hence conjecture is true.


Because $n-1=\frac{a_{n}-a_{n-1}}{n-(n-1)} \approx \frac{d}{dn} a_n$ is linear, it is reasonable to guess that $a_n$ is a quadratic because the integral of a linear function is a quadratic.

So guess $a_n=an^2+bn+c$.

This means,

$$\left(an^2+bn+c \right)-\left(a(n-1)^2+b(n-1)+c \right)$$




We want:





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.