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
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
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