Question

Solve the following recurrence relation:

`A_(n)=a_(n-1)+n; a_(1) = 0`

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) - \frac{(n-2)(n-1)}2`

`\implies a_n = \frac12 n^2 + \frac12 n - 1`

`\implies \boxed{a_n = \frac{(n+2)(n-1)}2}`