After attempting question 1.16 of Concrete Mathematics,
$g(1)=\alpha$
$g(2n+j)=3g(n)+\gamma n+ \beta_j, j=0,1$
I am having some difficulty getting the correct answer.
The following is my working:
$ g(n)=A(n)\alpha + B_0(n)\beta_0 + B_1(n)\beta_1 + C(n)\gamma$
Using $\alpha =1$ and $\beta_0,\beta_1,\gamma=0$
I get $A(2^m+l)=3^m$
Using $g(n)=1$
I get $g(n)=A(n)-2B_0(n)-2B_1(n)=1$
Using $g(n)=n$
I get $g(n)=A(n)+B_1(n)-C(n)=n$
Using $g(n)=n^2$
I get $g(n)=A(n)-2B_0(n)+3B_1(n)+3C(n)=n^2$
However, with these 4 equations I am unable to get an answer that tallies with the values n=5 of the recurrence, i.e. $g(5)=9α+3β0+β1+5γ$
We don’t actually need $g(n)=n^2$, and it’s where the calculation goes wrong. The problem with it is that $g(n)=n^2$ simply isn’t consistent with the recurrence: there is no choice of $\alpha,\beta_0,\beta_1$, and $\gamma$ that generates it. Specifically, the ones that work for $n\le 4$ fail at $n=5$.
However, we can get $A,B_0$, and $B_1$ directly from formula $(1.18)$ in the text. I’d forgotten, but it turns out that I actually explained that some years ago in answer to another question. The nature of $(1.18)$ means that the definitions of $B_0,B_1$, and $C$ are a bit ugly, since they’re expressed directly in terms of the binary representation of $n$, but they’re not bad to work with in practice.