Here is the recursive definition, for reference
\(T(1) = 5 \)\( T(n) = 3 T(n/2) + 7\) for \(n \ge 2\)
First, substitute the recursive part of the definition into itself and guess the pattern to get the result after k substitutions.
\( \begin{eqnarray*} T(n) &=& 3\cdot T(n/2) + 7 \\ &=& 3(3\cdot T(n/4) + 7) + 7 \\ &=& 3(3(3\cdot T(n/8) + 7) + 7) + 7 \\ &=& \ldots \\ &=& 3^k \cdot T(n/{2^k})+ 7 \sum_{i=0}^{k-1}3^i \\ \end{eqnarray*} \)
The input to T will hit the base case input value when \(n/2^k = 1\). That is, we need to have \(n = 2^k\). So \(k = \log_2 n\).
Substituting in the base case value for k and the fact that T(1)=5, we get:
\( \begin{eqnarray*} T(n) &=& 3^{\log_2 n} \cdot T(1) + 7 \sum_{i=0}^{\log_2 n-1}3^i = 5\cdot 3^{\log_2 n} + 7 \sum_{i=0}^{\log_2 n-1}3^i \\ \end{eqnarray*} \)
Find and fix any errors in the above, then return to the hints page for help with the final clean-up step.