It's a problem involving recurrence resolution from 《Concrete Mathmatics》whose number is 16 in chapter 1.Here is the description:
And then is the resolution:
Now my question is that what does "this defines a(n),b(n),and c(n)" mean, I know it's easy to get a(n),but how about b(n) and c(n)? Can anyone give me some clues? Thanks very much.
Suppose that $n=(1\,b_{m-1}\ldots b_1\,b_0)_2$. Then
$$\begin{align*} g(n)&=(\alpha\,\beta_{b_{m-1}}\,\beta_{b_{m-2}}\ldots\beta_{b_1}\,\beta_{b_0})_3\\ &=3^m\alpha+\beta_0\sum\{3^k:b_k=0\text{ and }k<m\}\\ &\qquad+\beta_1\sum\{3^k:b_k=1\text{ and }k<m\}\;, \end{align*}$$
so
$$\begin{align*} a(n)&=3^m\;,\\ b(n)&=\sum\{3^k:b_k=0\text{ and }k<m\}\;,\text{ and }\\ c(n)&=\sum\{3^k:b_k=1\text{ and }k<m\}\;. \end{align*}$$
To get the expressions for $b(n)$ and $c(n)$ I simply gathered together all of the entries in $(\alpha\,\beta_{b_{m-1}}\,\beta_{b_{m-2}}\ldots\beta_{b_1}\,\beta_{b_0})_3$ that involve $\beta_0$ and $\beta_1$, respectively: for $i=0,1$, $\beta_{b_k}=\beta_i$ precisely when $b_k=i$.
As an example, if $n=13=(1101)_2$, then $m=3$, $b_1=0$, and $b_0=b_2=1$, so $a(13)=27$, $b(13)=3^1=3$, and $c(13)=3^2+3^0=10$.
You can of course get these directly from the repertoire method. For instance, take $\alpha=1$ and $\beta_0=\beta_1=\gamma=0$; then $g(n)=a(n)$, and the recurrence becomes simply
$$\begin{align*} &a(1)=1\;,\\ &a(2n+j)=3a(n)\;. \end{align*}$$
If $n=2^m+\ell$, where $0\le\ell<2^m$, it’s easily checked that $a(n)=3^m$, which is exactly what I read out of the representation $(\alpha\,\beta_{b_{m-1}}\,\beta_{b_{m-2}}\ldots\beta_{b_1}\,\beta_{b_0})_3$.
If you take $\beta_0=1$ and $\alpha=\beta_1=\gamma=0$, you get
$$\begin{align*} &b(1)=0\;,\\ &b(2n)=3b(n)+1\;,\\ &b(2n+1)=3b(n)\;; \end{align*}$$
it’s a bit harder to see, but this has as closed form the function $b(n)$ that I read out of $(\alpha\,\beta_{b_{m-1}}\,\beta_{b_{m-2}}\ldots\beta_{b_1}\,\beta_{b_0})_3$. My expression for $c(n)$ can be derived similarly.
If we now set $g(n)=n$, the original recurrence becomes
$$\begin{align*} &1=\alpha\;,\\ &2n=3n+\gamma n+\beta_0\;,\\ &2n+1=3n+\gamma n+\beta_1\;, \end{align*}$$
whose unique solution (which is obtained by equating coefficients of like powers of $n$) is $\alpha=1$, $\beta_0=0$, $\beta_1=1$, and $\gamma=-1$, so that $n=g(n)=a(n)+c(n)-d(n)$, as claimed. Thus,
$$\begin{align*} d(n)&=a(n)+c(n)-n\\ &=3^m+\sum\{3^k:b_k=1\text{ and }k<m\}-n\;. \end{align*}$$
In the example above with $n=13$ we get $d(13)=27+10-13=24$.
