Question

Solve the following recurrence relation: %200" id="TexFormula1" title="A_{n}=a_{n-1}+n; a_{1} = 0" alt="A_{n}=a_{n-1}+n; a_{1} = 0" align="absmiddle" class="latex-formula">

Answer 1

By iteratively substituting, we have

$a_n = a_{n-1} + n$

$a_{n-1} = a_{n-2} + (n - 1) \implies a_n = a_{n-2} + n + (n - 1)$

$a_{n-2} = a_{n-3} + (n - 2) \implies a_n = a_{n-3} + n + (n - 1) + (n - 2)$

and the pattern continues down to the first term $a_1=0$,

$a_n = a_{n - (n - 1)} + n + (n - 1) + (n - 2) + \cdots + (n - (n - 2))$

$\implies a_n = a_1 + \displaystyle \sum_{k=0}^{n-2} (n - k)$

$\implies a_n = \displaystyle n \sum_{k=0}^{n-2} 1 - \sum_{k=0}^{n-2} k$

Recall the formulas

$\displaystyle \sum_{n=1}^N 1 = N$

$\displaystyle \sum_{n=1}^N n = \frac{N(N+1)}2$

It follows that

$a_n = n (n - 2) - \dfrac{(n-2)(n-1)}2$

$\implies a_n = \dfrac12 n^2 + \dfrac12 n - 1$

$\implies \boxed{a_n = \dfrac{(n+2)(n-1)}2}$