Task: Solve the recurrence equation:
$$T(n) = 3T\left( \frac{n}{3} \right) + 3n$$
Assume $T(0) = T(1) = O(1)$. My approach is:
$$T\left( \frac{n}{3} \right) = 3T\left( \frac{n}{9} \right) + \left( \frac{3n}{3} \right) = 3T\left( \frac{n}{9} \right) + n$$
$$T\left( \frac{n}{9} \right) = 3T\left( \frac{n}{27} \right) + \left( \frac{3n}{9} \right) = 3T\left( \frac{n}{27} \right) + \left( \frac{n}{3} \right)$$
Thus:
$$T(n) = 3\left(3T\left( \frac{n}{9} \right) + n\right) + 3n = 9T\left( \frac{n}{9} \right) + 6n$$
$$T(n) = 9\left(3T\left( \frac{n}{27} \right) + n\right) + 3n = 27T\left( \frac{n}{27} \right) + 12n$$
I don't recognise the pattern from $3n$ to $6n$ and $12n$, then should $9n$ come out there. Can someone help me to find the mistake?
You were on the right track. We will complete the reasoning here. As you were doing we expand the recurrence. The first iteration being:
$$T\left(n\right) = 3n + 3 T \left( \frac{n}{3} \right)$$
The next one being:
$$T\left(n\right) = 3n + 3n + 3^2 T \left( \frac{n}{3^2} \right)$$
And after one more:
$$T\left(n\right) = 3n + 3n + 3n + 3^3 T \left( \frac{n}{3^3} \right)$$
The number of times $k$ required to divide $n$ by $3$ to get $n$ down to $O(1)$, i.e.: $n = 3^k$, is $\log_3 n$. Now we generalise to:
$$T \left( n \right) = 3n \log_3 n + n$$
We can verify the explicit form using the substitution method:
$$T\left(n\right) = 3n + 3 \left( 3 \frac{n}{3} \log_3 \frac{n}{3} + \frac{n}{3} \right)$$
$$T\left(n\right) = 3n \log_3 \frac{n}{3} + n + 3n$$
$$T\left(n\right) = 3n \log_3 n - 3n \log_3 3 + n + 3n$$
$$T\left(n\right) = 3n \log_3 n + n$$