Solving linear recurrences with repertoire method

Question

$$\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?

Answer 1

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$.

Answer 2

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.