Solve the recurrence using backwards substitution

240 Views Asked by At

Here is what I have so far for this recurrence relation problem.

$$ \left\lbrace \begin{array}{l} x(0) = 0 \\ x(n) = x(n-1) + n \end{array} \right. $$ I have tried substituting to get $x (n-1) = x (n-2) + n-1$, but this is where I'm getting stuck at.

1

There are 1 best solutions below

0
On

Let's compute some of the first terms

$$x_1=x_0+1=0+1=1$$ $$x_2=x_1+2=0+1+2=3$$$$x_3=x_2+3=0+1+2+3=6$$

We see a pattern! We can rewrite the formula for $x_n$ as $$x_n=\sum\limits_{k=0}^n k$$This sequence is known as the triangular numbers. The explicit formula for it is $$x_n=\frac{n\cdot(n+1)}2$$