Solve the following recurrence relations. a. x(n) = x(n − 1) + 5 for n > 1, x(1) = 0b. x(n) = 3x(n − 1) for n > 1, x(1) = 4c. x(n) = x(n − 1) + n for n > 0, x(0) = 0

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

(b)x(n)=4 X 3ⁿ⁻¹

(c)x(n)=n(n+1)/2

Step-by-step explanation:

(a)x(n) = x(n − 1) + 5 for n > 1, x(1) = 0

Put n=n-1

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

Recall: x(n-1)= x(n)-5

Substitute:

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

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

Put n=n-2

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

Recall: x(n-2)= x(n)-5-5

Substitute:

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

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

Generalising

x(n)=x(n-i)+5i for i<n

Put i=n-1

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

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

x(n)=5(n-1)

(b)x(n) = 3x(n − 1) for n > 1, x(1) = 4

Put n=n-1

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

Recall: x(n-1)= x(n)/3

Substitute:

x(n)/3=3x(n-2)

x(n)=3 X 3x(n-2)

Put n=n-2

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

Recall: x(n-2)= x(n)/3²

Substitute:

x(n)/3²=3x(n-3)

x(n)= 3³x(n-3)

Generalising

x(n)=3ⁱ x(n-i) for i<n

Put i=n-1

x(n)=3ⁿ⁻¹ x(n-(n-1))

x(n)=3ⁿ⁻¹ x(1)

x(n)=3ⁿ⁻¹*4

x(n)=4 X 3ⁿ⁻¹

(c) x(n) = x(n − 1) + n for n > 0, x(0) =0

Put n=1

x(1)=x(1-1)+1

x(1)=0+1=1

Put n=2

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

x(2)=x(1)+2=1+2=3

Put n=3

x(3)=x(3-1)+3=x(2)+3=3+3=6

Generalising

x(n)=n(n+1)/2

you can first factor out the n to get n(1+5). we know that 1+5 is 6, so we just have 6n.

acd, jgvjgbgbgvhgbhjjn