Where does this recursion formula come from? I come across an explanation of recursion complexity.  This screenshot is in question:

How do you get this?
T(n) = 3T(n/4) + n

The $log_n^4$ shown seems to be base 4, and this baffles me.  What does the n superscript stand for?  I am inclined to think the base of this log should be 3.  Can someone explain this to me?

Another example was provided where the tree expands at an exponent of 2:

The formula given is:
T(n) = 2T(n/2) + 2

The log(n) given is said to be of base 2.  This makes sense to me, but not the base 4 in given by the first picture.
 A: $\begin{array}\\
T(n)
&=3T(n/4)+1\\
&=3(3T(n/16)+1)+1\\
&=9T(n/16)+4\\
&=9(3T(n/64)+1)+4\\
&=27T(n/64)+13\\
&.....\\
&=3^kT(n/4^k)+\sum_{j=0}^{k-1}3^j
\qquad\text{conjecture}\\
&=3^k(3T(n/4^{k+1})+1)+\sum_{j=0}^{k-1}3^j
\qquad\text{induction step}\\
&=3^{k+1}T(n/4^{k+1})+3^k+\sum_{j=0}^{k-1}3^j\\
&=3^{k+1}T(n/4^{k+1})+\sum_{j=0}^{k}3^j
\qquad\text{confirmed}\\
\end{array}
$
Note that the induction stops when
$4^k \ge n$.
Also note that
$\sum_{j=0}^{k-1}3^j
=\dfrac{3^k-1}{3-1}
=\dfrac{3^k-1}{2}
$.
A: In this example, we're considering an algorithm that, given a problem of size $n$, does 1 unit of "local" work and divides the remaining work into 3 smaller problems of the same kind, where each of these subproblems has size $n/4$. (Instead of 3 and 4 we could have any numbers; this is just an example.) So if $T(n)$ is the total amount of work done in solving a problem of size $n$, we have the equation $T(n)=3T(n/4)+1$ by assumption.
The tree figure shows a way of thinking about the algorithm and understanding the growth rate of $T$. At $k$ levels below the root, we have $3^k$ subproblems and each subproblem has size $n/4^k$. Since our algorithm stops splitting the problem up when it reaches a base case (i.e. a problem of size 1), the tree has $\log_4n$ levels, and the number of base cases at the bottom level is $3^{\log_4n}$.
