149k views
4 votes
Solve recurrence relation x (n) = x(n/3) +1 for n >1,x(1) =1. (Solve for n = 3k)

User Alfred Luu
by
7.5k points

1 Answer

4 votes

To solve this recurrence relation, we can use the iterative method known as substitution method. First, we make a guess for the solution and then prove it by mathematical induction.

Let's guess that x(n) = log base 3 of n. We can verify this guess by induction:

Base Case: x(1) = log base 3 of 1 = 0 + 1 = 1. So, the guess holds for n = 1.

Induction Hypothesis: Assume that x(k) = log base 3 of k holds for all k < n.

Induction Step: We need to show that x(n) = log base 3 of n holds as well. We have:

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

= log base 3 of (n/3) + 1 (by induction hypothesis)

= log base 3 of n - log base 3 of 3 + 1

= log base 3 of n

So, x(n) = log base 3 of n holds for all n that are powers of 3.

Therefore, the solution to the recurrence relation x(n) = x(n/3) + 1 for n > 1, x(1) = 1, is x(n) = log base 3 of n for n = 3^k.

User Aceinthehole
by
7.9k points