# confused about an explanation of a recurrence problem

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.

-
I wonder how we "know everything", but I could presume that we can take $a(n)$ the unique solution to the recurrence if $\alpha=1$, $\beta_0=\beta_1=\gamma=0$ and so on. – Hagen von Eitzen Sep 7 '13 at 12:32
@HagenvonEitzen:"hence we know everything" means that you can get d(n) once you've got a(n),b(n) and c(n), then you can induce d(n) from "a(n) + c(n) - d(n) = n". – tuan long Sep 7 '13 at 12:53

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\}+\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_0=b_2=0$, and $b_1=1$, so $a(13)=27$, $b(13)=3^2+3^0=10$, and $c(13)=3^1=3$.

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+3-13=17$.

-
M.Scott:Thank you very much, professor.I'd have considered that no one would like to help me.Really appreciate your help. – tuan long Sep 8 '13 at 3:31
@tuanlong: You’re welcome. – Brian M. Scott Sep 8 '13 at 18:01