Combination

Question

The Solution of the recurrence relation An-2An-1=2ⁿ  where A₀=1 ?

Answer 1

solution for this recurrence rel is given by A_h + A_p  {hypothesis + particular  solution}

for  A_h  , given equation can be put equal to zero

i.e = An - 2An-1 = 0

it is of degree 1

divide whole equation by An-1

Now equation remains as  A - 2 = 0   --> characteristic equation

i.e A = 2 

i.e A_{h =}  c(2)ⁿ

A0 = 1 therefor  by putting value of n in above equation we get value of c as 1

now we have to solve particular solution

the solution would be d.aⁿ because it is of the form 2ⁿ

i.e  d . 2ⁿ   - 2 . d. 2^n-1  = 2ⁿ  we don;t have a solution for this equation as both terms on left side cancel each other therefor we can put it as zero

i.e An = Ah + Ap

Answer  =          An = 1.(2)ⁿ + 0   == (2)ⁿ

Comments

@Mohit. We have to put the value of A₀ once we get  A_h+A_p i.e. entire solution. Plz confirm.