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 :)