Question

solve the recurrence relation Pn = Pn-1 + n with initial condition P1 = 2 using interation.

Answer 1

$P(n)=P(n-1)+n$

$$P(n-1)=P(n-2)+n-1$$

$$P(n)=P(n-1)+n=P(n-2)+n-1+n$$

$P(n)=P(n-2)+2n-(0+1)$

$$P(n-2)=P(n-3)+n-2$$

$$P(n)=P(n-1)+n=P(n-2)+2n-1$$

$$=P(n-3)+3n-3$$

$P(n)=P(n-3)+3n-(0+1+2)$

$$P(n-3)=P(n-4)+n-3$$

$$P(n)=P(n-1)+n=P(n-2)+2n-1$$

$$=P(n-3)+3n-3=P(n-4)+4n-6$$

$P(n)=P(n-4)+4n-(0+1+2+3)$

$$...$$

$$P(n)=P(n-k)+kn-\displaystyle\sum_{i=0}^{k-1}i, \ k=1,2,..., n-1$$

$$P(1)=P(n-(n-1))$$

Then

$$P(n)=P(1)+(n-1)n-\displaystyle\sum_{i=0}^{n-2}i, n=2, 3, ...$$

$$\displaystyle\sum_{i=0}^{n-2}i,=\dfrac{(n-2)(n-2+1)}{2}$$

$$=\dfrac{(n-2)(n-1)}{2}, n=2, 3, ...$$

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

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

$$=2+\dfrac{(n-1)(n+2)}{2}, n\geq2$$

$$P(n)=2+\dfrac{(n-1)(n+2)}{2},n\geq1$$