CRT-2022

Question

 

Kindly help 

Answer 1

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

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

T(n-2)=2T(n-3)+(n-2)

T(n-3)=2T(n-4)+(n-3)

……………………….

substituting the values we get like after k term,

T(n)=$2^{k}$T(n-k)+$2^{k-1}(n-k+1)$+……..4*(n-2)+2(n-1)+n

now let say ,

n-k=1

k=n-1

T(n)=$2^{n-1}*1+2^{n-2}*2 +2^{n-3}*3+.......+4*(n-2)+2*(n-1)+n$

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

         =$2^{n-1}+n\sum_{i=0}^{n-2}2^{i}-\sum_{i=0}^{n-2}i2^{i}$

          =$2^{n+1}-n-2$

https://math.stackexchange.com/questions/239974/solve-the-recurrence-tn-2tn-1-n