Substitution method for solving recurrences piece wise function

56 Views Asked by At

I don't know how to use the substitution method for the following function: piece wise function: $T(n) = c$, if $n=0$ $T(n) = d$, if $n=1$ $T(n)=2T(n-1)-T(n-2)+1$, if $n > 1$

1

There are 1 best solutions below

0
On

Let $T(n)=f(n)+an+b$ where $a,b$ are arbitrary constants

$$\implies f(m)+am+b=2[f(m-1)+a(m-1)+b]-[f(m-2)+a(m-2)+b]+1$$

$$\iff f(m)-2f(m-1)+f(m-2)=a+1$$

Set $a+1=0$ and use this