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.