Question

Solve the following recurrence relation:

 T(n)=9T(n-1)-20T(n-2)

T(0)=-3

T(1)=-10

a)2.5ⁿ-5.4ⁿ

b)3.5^n-4.3ⁿ

c)3.4ⁿ-2.5ⁿ

d)4.5ⁿ-2.3ⁿ

can it be solved by substitution..?

Comments

ans a)

best way to solve it

put n=0,n=1

in option

and get answer

---

@gari,

it is simply homogenous recurrence equation,

corresponding polynomial is,

x²-9x+20=0

roots are x=4 and x=5

T(n) = a4ⁿ + b5ⁿ

now to find constants 'a' and 'b' use T(0)=-3 and T(1)=-10

you will get a=-5 and b=2, 

therefore final solution to above homogenous equation is,  $T(n)=-5.4^{n}+2.5^{n}$

it can also be solved by substitution, but it will take time..

for these types of qsns(homogenous recurrence relations), directly use straightforward approach.

---

@ srestha  i tried but i failed..please see

T(2)=9T(1)-20T(0) = 9*(-10)-20*(-3)=-90+60=-30

NOW on putting n=2 in part a i get -22.91...

where am i wrong?

---

@gari,

it is, $2*5^n-5*4^n$

---

ohh.... Thanku so much @ joshi_nitish ... It was a poor doubt . 

---

its not a decimal point it gives -30 in both ways