Question

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

Answer 1

Solution:

(a)

Given,

=>x(n) = x(n-1) + 3 for n > 1 and x(1) = 0

Explanation:

Solving recurrence relation using substitution:

=>x(n) = x(n-1) + 3...(1)

=>x(n-1) = x(n-2) + 3....(2)

From (1) and (2)

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

and so on.

=>x(n) = x(n-p) = 3 + 3 + ... p times

=>x(n) = x(n-p) = 3*p....(3)

We know that x(1) = 0

=>n - p = 1

=>p = n - 1...(4)

From (3) and (4)

=>x(n) = 0 + 3*(n-1)

=>Hence x(n) = 3*(n-1)

(b)

Given,

=>x(n) = 5(x - 1) for n > 1, x(1) = 6

Explanation:

Solving recurrence relation using substitution:

=>x(n) = 5(x - 1)....(1)

=>x(n-1) = 5(x-2)...(2)

From (1) and (2)

=>x(n) = 5^2x(n-2)

and so on

=>x(n) = 5^px(n-p)....(3)

We know that x(1) = 6

=>n - p = 1

=>p = n - 1

=>x(n)= 5^(n-1)*6

=>Hence x(n) = 6*5^(n-1)

(c)

Given,

=>x(n) = x(n/5) + 1 for n > 1 and x(1) = 1

Explanation:

Solving recurrence relation using substitution method:

=>x(n) = x(n/5) + 1....(1)

=>x(n/5) = x(n/5^2) + 1...(2)

From (1) and (2)

=>x(n) = x(n/5^2) + 1 + 1

and so on.

=>x(n) = x(n/5^p) + 1 + 1 + ...p times

=>x(n) = x(n/5^p) + 1*p..(3)

We know that x(1) = 1

=>n/5^p = 1

=>x = 5^p

Taking log both sides on base 5

=>p = log₅(x)...(4)

From (3) and (4)

=>x(n) = 1 + 1*log₅(x)

=>Hence x(n) = log₅(x) + 1

I have explained each and every part with the help of statements attached to the answer above.