How to solve this recurrence relation?

Question

Solve the equation: $$a_n = 5a_{n/3} + 7, \;\; a_1 = 5$$

Note: $a_0$ is not given.

Answer 1

$$\def\t#1{T\left (n/3^{#1}\right )}
\begin{align}
T(n) &= 5\cdot \t1 + 7\\[1em]
\hdashline
&= 5 \times \Biggl (5\cdot \t2 + 7 \Biggr )  + 7\\[1em]
&= 5^2 \cdot \t2 + 5^1 \cdot 7 + 7\\[1em]
\hdashline
&= 5^2 \times \Biggl (5\cdot \t3 + 7 \Biggr )  + 5^1 + 7\\[1em]
&= 5^3 \cdot \t3 + 5^2 \cdot 7 + 5^1 \cdot 7 + 7\\
\hdashline\\[1em]
&\vdots\\
&= 5^k\cdot\t k + 7 \cdot \sum_{i=0}^{k-1} 5^i
\end{align}$$

When $k = \log_3 n$, we have:

$$\begin{align}
T(n) &= 5^{\log_3 n}\cdot T(1) + 7 \cdot \sum_{i=0}^{(\log_3 n)-1} 5^i\\[1em]
&= 5^{\log_3 n}\cdot T(1) + 7 \times \left ( \frac{5^{1 + (\log_3 n - 1)} - 1}{5 - 1} \right )
\end{align}$$

It is given that $T(1) = 5$, hence, we get:

$$\begin{align}
T(n) &= \frac1 4 \cdot \Bigl ( (4\cdot 5 + 7) \cdot 5^{\log_3 n}  - 7\Bigr )\\[1em]
&= \frac1 4 \cdot \Bigl(27 \cdot n^{\log_3 5} - 7 \Bigr )\\[1em]
&\lessapprox \frac1 4 \cdot \Bigl (27 \cdot n^{1.465} - 7 \Bigr )
\end{align}$$

Comments

Is this the correct solution? Can I rely on it?

---

@sampad: Yes.

Here's two ways you can verify it:

1. Use the Master Method (Wikipedia) (Online solver)
    
    
2. WolframAlpha: http://www.wolframalpha.com/input/?i=a%28n%29%3D5*a%28n%2F3%29%2B7%2C+a%281%29%3D5
   
   You will get answer in terms of $5^{\log(n)/\log(3)}$, and that is equal to $n^{\log_3 5}$.