Question

Solve the following recurrence relations.

{eq}a. x(n)=x(n-1)+5 text{ for } n>1,quad x(1)=0\

b. x(n)=3x(n-1) text{ for } n>1,quad x(1)=4\

c. x(n)=x(n-1)+n text{ for } n>0,quad x(0)=0

{/eq}

EXPERT ANSWER

a. x(n)=x(n-1)+5…………eq1

replace n by n-1

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

replace n by n-2

x(n-2)=x(n-3)+5+5+5

put the value of x(n-1) in eq1

so

x(n)= x(n-2)+5+5……….eq2

put the value of x(n-2) in eq1

x(n)=x(n-3)+5+5+5………eq3

generalize the equation 1,2,3

x(n)=x(n-i)+5i there is i<n

now put i=n-1

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

x(n)= 5(n-1)

now put n=1

so,

x(1)=0.

b. x(n)=3x(n-1)……..eq1

replacing n by n-1

x(n-1)=3x(n-2)…..eq2

replacing n by n-2

x(n-2)=3x(n-3)……….eq3

replacing x(n-1) by eq2

x(n)=3.3x(n-2)

replaciing n by