5. Solve the following recurrence relations.

a. x(n) = x(n-1) + 5 for n > 1, x(1) = 0
b. x(n) = 3x(n-1) for n > 1, x(1) = 4
c. x(n) = x(n-1) + n for n > 0, x(0) = 0

Expert Answer

• 
  Anonymous answered this

  Was this answer helpful?

  40 answers

  Ans a: x(n)=x(n-1)+5

  = [x(n-2)+5]+5

  =[x(n-3)+5]+5+5 = x(n-3)+5*3

  = .......

  = x(n-i)+5*i , if i=n-1 then,

  = x(n-(n-1))+5*(n-1)

  = x(1)+5(n-1)

  = 0 +5(n-1) given x(1)=0

  x(n)= 5(n-1)   

  Ans b: x(n)= 3x(n-1)

  = 3[3x(n-2)]= 3² *x(n-2)

  = 3*3[3x(n-3)]= 3³* x(n-3)

  ............

  = 3ⁱ * x(n-i)

  if we put i=n-1 then

  = 3^(n-1) x(n-(n-1))

  = 3^(n-1) x(1)

  x(n) =3^(n-1) *4 ,given x(1)=4

  Ans c: x(n) = x(n-1) + n

  = [x(n-2)+n]+n

  =[x(n-3)+n]+n+n = x(n-3)+n*3

  = .......

  = x(n-i)+n*i , if i=n then,

  = x(n-n)+n*n

  = x(0)+n*n

  = 0 +n² given x(0)=0

  x(n)= n²