Question

Solve the following recurrence relation using recurrence tree and iteration methods

T(n) = T(n-1) + n

Answer 1

 recurrence tree

t(n) n

t(n-1) n-1

t(n-2) n-2

...

t(1) 1

$t(n)=\sum\limits_{i=1}^n i=\frac{n(n+1)}{2}$

iteration methods

$t(n)=n+t(n-1)=n+(n-1)+t(n-2)=...=\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}$