Repertoire method for solving recursions I am trying to solve this four parameter recurrence from exercise 1.16 in Concrete Mathematics:
\[ g(1)=\alpha \]
\[ g(2n+j)=3g(n)+\gamma n+\beta_j \]
\[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \]
I have assumed the closed form to be:
$$g(n) = A(n)\alpha+B(n)\gamma+C(n)\beta_0+D(n)\beta_1$$
Next i plugged $g(n)=1$ in the recurrence equations from which I obtained $\alpha=0 ,\beta_0=-2,\beta_1=-2$ and $\gamma=0$
Substituting these values back into the closed form, I got:
$$A(n)-2C(n)-2D(n)=1$$
Similarly plugging $g(n)=n$, I got $\alpha=1,\beta_0=0,\beta_1=1$ and $\gamma=-1$ and plugging this back into the closed form, we get:
$$A(n)-B(n)+D(n) = n$$
Also, from the text in chapter 1, a recursion of general form
$$f(j)=\alpha_j$$
$$f(dn+j) = cf(n)+\beta_j$$
has a radix representation of
$$f((b_mb_{m-1}...b_1b_0)_d) = (\alpha_{b_m}\beta_{b_m-1}...\beta_{b_1}\beta_{b_0})_c$$
Applying the generalization to the current problem we have 
$$A(n)\alpha+C(n)\beta_0+D(n)\beta_1=(\alpha\beta_{b_m-1}...\beta_{b_1}\beta_{b_0})_3$$ where $n=(1b_{m-1}...b_1b_0)_2$
I am unable to see how to proceed further from here. Any help will be appreciated :)
 A: You don't need to substitute $g(n) = 1$.  If you do, however, you should get $\alpha = 1$, not $\alpha = 0$.

We know that $$g(n) = \alpha A(n) + \gamma B(n) + \beta_0 C(n) + \beta_1 D(n)\tag{1}$$
We also know that:
$$\alpha A(n) + \beta_0 C(n) + \beta_1 D(n) = (\alpha\beta_{b_{m-1}}\ldots \beta_{b_0})_3\tag{2}$$  Thus, all that remains is to determine $B(n)$, then we have solved the problem.
From substituting $g(n) = n$, we have that:
$$A(n) - B(n) + D(n) = n$$
Thus:
$$\begin{align}
B(n) &= \underbrace{A(n) + \color{red}{C(n)} + D(n)}_{\text{simplify using $(2)$}} \color{red}{- C(n)} - n\\
&= \underbrace{(1\ldots1)_3}_{m+1 \text{ digits}} - C(n) -n \\
&= \frac{3^{m+1}-1}{2} - \left(\sum_{{k,\text{ where } b_k = 0}} 3^k\right) - n
\end{align}$$
This leads us to the solution:
$$g(n) = (\alpha\beta_{b_{m-1}}\ldots \beta_{b_0})_3 + \gamma\left(\frac{3^{m+1}-1}{2} - \left(\sum_{{k,\text{ where } b_k = 0}} 3^k\right) - n\right)$$
...where $n=(b_mb_{m-1}\ldots b_0)_2$.
I'd like to get the sum out of the solution, but I don't know of a good way to do so.  (I doubt if it is possible.)
A: Other answers build a summation and it isn't necessary. Here is a solution exclusively using the repertoire method and in the same spirit as 1.18 in the book
Let
$$g(n)=A(n)α+B(n)γ+C(n)β_0+D(n)β_1 $$
Recall that $(\alpha, \gamma, \beta_0, \beta_1) \to (\alpha, 0, \beta_0, \beta_1)$ for $n = (b_mb_{m−1}...b_1b_0)_2$ is the radix changing solution
$$A(n)α+C(n)β_0+D(n)β_1=(αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 \tag{1}$$
Let $(\alpha, \gamma, \beta_0, \beta_1) \to (0, 0, 0, 1)$. Then
$$D(n) = (β_{b_{m−1}}...β_{b_1}β_{b_0})_3 = (b_{m−1}...b_1b_0)_3  \tag{2}$$ 
Think of $\beta_0 = 0$ and $\beta_1= 1$ as a function from radix-2 to radix-3, changing every power and preserving the coefficients.
Let $(\alpha, \gamma, \beta_0, \beta_1) \to (1, 0, 0, 0)$. Then
$$ A(n) = (100...0)_3 = 3^m \tag{3}$$
Given the identity derived from $g(n)=n$, we can solve $$ A(n)−B(n)+D(n)=n$$ for $\gamma B(n)$. Thus plugging $$ \gamma B(n) = \gamma A(n) + \gamma D(n) - \gamma n$$ into (1), 
$$ A(n)α+ \gamma B(n)+ C(n)β_0+D(n)β_1=(αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 + \gamma A(n) + \gamma D(n) - \gamma n $$ 
Finally, for $n = (b_mb_{m−1}...b_1b_0)_2$, we can plug in (3) and (2), 
$$ g(n) = (αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 + \gamma(1b_{m−1}...b_1b_0)_3  - \gamma (b_mb_{m−1}...b_1b_0)_2 $$
