0

This equation below must solved by converting it from a non-homogenous equation into a homogenous one and then use the characteristic equation.

T(1)= 5
T(n)= 2T(n−1)+3n+1,n>1

In the text and pictures that follow, I show how I solved and verified using the telescoping equation and summations. I need to reach the same answer using converting it from a non-homogenous equation into a homogenous one and then use the characteristic equation, but I am not sure what is the best way to approach this?

Part 1:
T(1) = S(n)
( (2T(n-1)) / 2^n ) = ( T(n-1) / 2^(n-1) ) = S(n-1)
( T(n) / 2^n ) = s(1) = (s / 2)

part 2 part 3

mrcoder123
  • 1

1 Answers1

1

Hint. Find constants $A$ and $B$ such that $$t(n)=2(t(n-1))$$ that is $$T(n)+An+B=2T(n-1)+2A(n-1)+2B \Leftrightarrow 3n+1=An+B-2A$$ where $t(n)=T(n)+An+B$.

Note that the above recurrence is homogeneous with respect to $t(n)$.

By the characteristic equation $z-2=0$, we have that $$t(n)=t(1)\cdot 2^{n-1}=(T(1)+A+B)2^{n-1}=(5+A+B)2^{n-1}$$ which implies that $$T(n)=t(n)-An-B=(5+A+B)2^{n-1}-An-B.$$

Robert Z
  • 145,942