Solving linear recurrences with repertoire method $$\begin{align*}
A_1 &= 0\\
A_{2n} &= 3A_n + n\\
A_{2n+1} &= 3A_n + n
\end{align*}$$
I am trying to solve a recurrence of this form, after writing out small number I can see no pattern except it should be related to $3^{\lfloor\log n\rfloor}$. And if I try to apply the repertoire method, I find myself stuck because no matter which function i try to plug in, the coefficient $3$ just get in the way because the cases are divided into even and odd
Can someone give me a hint or some help?
 A: Write $n$ in binary, so $n=\sum_{k=0}^ma_k2^k$, with each $a_k$ either $0$ or $1$, and $a_m=1$.
Firstly, if $n=2^m$, there is a simple formula for $A_n$ in terms of powers of $2$ and $3$.
Secondly, if $n=2^m+2^p$, with $p<m$, see how the final value is adjusted by the $2^p$
In general, find a formula for $A_n$ in terms of the $a_k$.  
A: This recurrence relation can be generalized to
$$A_1 = \alpha$$
$$A_{2n+j} = 3A_n + \gamma n+\beta_j$$
$$\mbox{for}\ j=0,1\ \mbox{and}\ n\geq 1$$
Which was the very first problem that I solved on this site. The general solution taken from my oldest post is
$$\mbox{Let}\ S= \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\}$$
$$A_n=3^m\left(\alpha + \frac{1}{2}\beta_0+\gamma\right)+ (\beta_1 -\beta_0+\gamma) \sum S- n\gamma -\frac{1}{2}\beta_0$$
So now for your specific recurrence, we have
$$\alpha =0, \beta_0=0, \beta_1=0, \gamma=1$$
Therefore the solution to your specific recurrence is
$$\mbox{Let}\ S= \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\}$$
$$A_n=3^m-n+\sum S$$
Examples of how to evaluate $A_n$
Example 1:
$$A_4=A_{2^2+0}=A_{(1\color{red}{00})_2}$$
From this we can see that $m=2$ and $S=\varnothing$. So now
$$A_4=3^2-4+\sum\varnothing=9-4+0=5$$
Example 2:
$$A_7=A_{2^2+3}=A_{(1\color{red}{11})_2}$$
From this we can see that $m=2$ and $S=\{3^1, 3^0\}$. So now
$$A_7=3^2-7+\sum\{3^1, 3^0\}=9-7+3+1=6$$
Example 3:
$$A_{13}=A_{2^3+5}=A_{(1\color{red}{101})_2}$$
From this we can see that $m=3$ and $S=\{3^2, 3^0\}$. So now
$$A_{13}=3^3-13+\sum\{3^2, 3^0\}=27-13+9+1=24$$
I hope this helps you understand.
