1 Solve the following recurrence relation P12 Pn2Pn1n2n for

1.) Solve the following recurrence relation:

P(1)=2

P(n)=2P(n-1)+n2n for n>=2

2. A sequence is recursively defined by:

T(0)=1

T(1)=2

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

Prove that T(n)<=(5/2)n for n>=0

1) P(1) = 2

p(2) = 2*(2)+ 2^(2*2) = 20

P(3) = 2*20+2^(2*3) = 104 ....

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

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

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

T(2) = 2*2+1 = 5 = 5/2*2 =5

T(3) = 2*5+2 = 12 > 5/2*3=7.5

so as n increases T(n) is much more smaller than 5/2n