Find a formula for a recursion I have the following reccurence:
$$f(n)=3f\left(\frac{n}{2}\right)+4, \quad f(1)=1  \text{ and } n=2^k.$$
The task is to find a formula, that depends only on $n$ and prove it by induction. I have calculated some values of this recursion,
$$f(2)=7, f(4)=25, f(8)=79,$$
but I did't find any relation between these numbers.
 A: You start from $$f(2n)=3f(n)+4$$
To remove the constant, notice that a constant solution would verify $a=3a+4\iff a=-2$.
So we will set $f(n)=g(n)-2$ to reduce the equation to $$g(2n)=3g(n)$$

Now take $n=2^k$ then $g(2^k)=3g(2^{k-1})=3^2g(2^{k-2})=\cdots=3^kg(2^0)=3^kg(1)$
Since we have $g(1)=f(1)+2=3$ then $g(2^k)=3^{k+1}$.
Finally substituting $k=\log_2(n)$ you get: $$\large{f(n)=3^{\log_2(n)+1}-2}$$
A: Solving the recurrrence
For recurrence relations on this particular form, you can use the Master Method. I will not describe what the method is, since it can be found in several books.
We can set the variables $a = 3$ and $b = 2$ and the function $f(n) = 4$. We will use a test case to test which of the 3 cases of the Master Method is the solution.
$n^{log_b(a)} = n^{log_2(3)}$
It can be seen that $f(n) \leq n^{log_2(3)}$. Therefore, we use case 1 as the solution. Case 1 states that the solution to the recurrence is $\Theta(n^{log_b(a)}) = \Theta(n^{log_2(3)})$.
Proving the result
To prove the result, induction is the most efficient proof technique for this particular problem. We will start out with the basis step for the lowest value, which is 0 for the equation
$f(n) = 3f(\frac{n}{2}) + 4 \leq \Theta(n^{log_2(3)})$.
Basis step
First of all, you haven't defined the result of $f(0)$, so I will just assume $f(0) = -2$.
Then, it can be seen that
$f(n) = 3f(\frac{0}{2}) + 4 = 3 * (-2) + 4 = -2 \leq \Theta(0^{log_2(3)})$
is true.
Inductive step
We now it must be true that
$f(n) = 3f(\frac{n}{2}) + 4 \leq \Theta(n^{log_2(3)})$.
Therefore, it also holds for any $k \geq n$. This implies the equation is true for $k + 1$:
$f(k) = 3f(\frac{k + 1}{2}) + 4 \leq \Theta((k + 1)^{log_2(3)})$.
We will insert $\Theta(k^{log_2(3)})$ into the function definition:
$f(k) = 3 * (\frac{k + 1}{2})^{log_2(3)}$
$= 3 * \frac{(k + 1)^{log_2(3)}}{2^{log_2(3)}}$
$= 3 * \frac{(k + 1)^{log_2(3)}}{3^{log_2(2)}}$
$= \frac{3 * (k + 1)^{log_2(3)}}{3}$
$= (k + 1)^{log_2(3)}$,
and our proof is complete.
