Given recurrence relationship:
$g(1) = 5;\\ g(2n) = 4g(n);\\ g(2n+1) = 4g(n).$
I feel lost because of $g(2n)$ and $g(2n+1)$.
Based on my coursebook, there is the common standard form, which can be used in order to find the relation:
$g(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$
$A(n),B(n)$ and $C(n)$ are functions, $\alpha, \beta, \gamma$ are constants. I suppose this form is for the case when there is 3 constants? Thus in this case the form should be $g(n) = A(n)\alpha$?
How does one use this knowledge in order to solve the relationship?
=====
$f(1)=α;\\ f(2n)=2f(n)+1;\\ f(2n+1)=2f(n)+β.$
This is the case when I do not have a number, but a constant - how does one solve the relationship?
Here is a contribution that is not a compact form but may perhaps be of some use. Supposing the recurrence
$$f(1) = \alpha, \\ f(2n) = 2f(n) + \beta, \\ f(2n+1) = 2f(n) + \gamma.$$
Introduce the base two representation of $n$ which is
$$n=\sum_{k=0}^{\lfloor\log_2 n\rfloor} d_k 2^k.$$
We then obtain the closed form (exact) by inspection which is
$$f(n) = \alpha \times 2^{\lfloor\log_2 n\rfloor} + \sum_{k=0}^{\lfloor\log_2 n\rfloor-1} ([[d_k = 0]]\times \beta + [[d_k = 1]]\times \gamma) \times 2^{k}.$$
We can deduce some special values from this e.g. $$f(2^m) = \alpha \times 2^m + \beta \sum_{k=0}^{m-1} 2^k = \alpha \times 2^m + \beta \times (2^m-1).$$
Similarly $$f(2^m-1) = \alpha \times 2^{m-1} + \gamma \sum_{k=0}^{m-2} 2^k = \alpha \times 2^{m-1} + \gamma \times (2^{m-1}-1).$$