Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It's a problem involving recurrence resolution from 《Concrete Mathmatics》whose number is 16 in chapter 1.Here is the description: enter image description here

And then is the resolution: enter image description here

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.

share|cite|improve this question
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*}$$


$$\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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.