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*} \)
Notice that \(3^{\log_2 n}= 3^{\log_3 n \cdot \log_2 3}= n^{\log_2 3}\).
From any standard summation table, we find that \(\displaystyle\sum_{i=0}^{p}r^i = \frac{r^{p+1} -1}{r-1}\)
So \(\displaystyle\sum_{i=0}^{\log_2 n-1}3^i = \frac{3^{\log_2 n} -1}{3-1} = \frac{n^{\log_2 3} -1}{2}\)
So \(\displaystyle T(n) = 5\cdot 3^{\log_2 n} + 7 \sum_{i=0}^{\log_2 n-1}3^i = 5\cdot n^{\log_2{3}} + 7 \frac{n^{\log_2{3}}- 1}{2} = \frac{17n^{\log_2 3} -7}{2} \)
If your final answer is incorrect, look for the location where your calculations start to differ from the above. Make sure you understand what went wrong. However, be aware that small errors are common with this method. It's always wise to check your supposed closed form against outputs of the original recursive definition and/or sketch an inductive proof of correctness.
Notice that unrolling is not a proof. Although many parts of the calculation would be ok in a formal proof, step 2 (guess the pattern) asks the reader to simply have faith in your theory of what the pattern is. Unrolling is a technique for finding out what the closed form is. Proving the closed form correct requires induction.
In computer science, the default base for the log is 2. So, in some contexts, you'll see this written simply as "log n". We've marked the base explicitly in this solution (even when it's 2) because some of the logs have a different base. However, expect to see the base omitted when it's (a) 2 for the whole problem or (b) the base doesn't matter e.g. in a big-O algorithm analysis.