9
$\begingroup$

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

$\endgroup$
1
3
$\begingroup$

Other answers build a summation and it isn't necessary. Here is a solution exclusively using the repertoire method and in the same spirit as 1.18 in the book

Let $$g(n)=A(n)α+B(n)γ+C(n)β_0+D(n)β_1 $$

Recall that $(\alpha, \gamma, \beta_0, \beta_1) \to (\alpha, 0, \beta_0, \beta_1)$ for $n = (b_mb_{m−1}...b_1b_0)_2$ is the radix changing solution $$A(n)α+C(n)β_0+D(n)β_1=(αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 \tag{1}$$

Let $(\alpha, \gamma, \beta_0, \beta_1) \to (0, 0, 0, 1)$. Then $$D(n) = (β_{b_{m−1}}...β_{b_1}β_{b_0})_3 = (b_{m−1}...b_1b_0)_3 \tag{2}$$

Think of $\beta_0 = 0$ and $\beta_1= 1$ as a function from radix-2 to radix-3, changing every power and preserving the coefficients.

Let $(\alpha, \gamma, \beta_0, \beta_1) \to (1, 0, 0, 0)$. Then $$ A(n) = (100...0)_3 = 3^m \tag{3}$$

Given the identity derived from $g(n)=n$, we can solve $$ A(n)−B(n)+D(n)=n$$ for $\gamma B(n)$. Thus plugging $$ \gamma B(n) = \gamma A(n) + \gamma D(n) - \gamma n$$ into (1), $$ A(n)α+ \gamma B(n)+ C(n)β_0+D(n)β_1=(αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 + \gamma A(n) + \gamma D(n) - \gamma n $$

Finally, for $n = (b_mb_{m−1}...b_1b_0)_2$, we can plug in (3) and (2), $$ g(n) = (αβ_{b_{m−1}}...β_{b_1}β_{b_0})_3 + \gamma(1b_{m−1}...b_1b_0)_3 - \gamma (b_mb_{m−1}...b_1b_0)_2 $$

$\endgroup$
2
  • 1
    $\begingroup$ I'm not sure why this was ever downvoted--it's a better answer than mine (as far as closed-forms go). I'll upvote as soon as I get my vote count replenished. $\endgroup$
    – apnorton
    Jan 30 '15 at 23:23
  • 1
    $\begingroup$ Thanks. I thought your answer (and the other one) were interesting ways to think of the problem, just not done in the same spirit as some of the examples in the book. I tried to think how Knuth might envision a solution (not to say mine is of that quality, just my attempt). $\endgroup$
    – tmastny
    Jan 31 '15 at 0:15
3
$\begingroup$

You don't need to substitute $g(n) = 1$. If you do, however, you should get $\alpha = 1$, not $\alpha = 0$.


We know that $$g(n) = \alpha A(n) + \gamma B(n) + \beta_0 C(n) + \beta_1 D(n)\tag{1}$$
We also know that: $$\alpha A(n) + \beta_0 C(n) + \beta_1 D(n) = (\alpha\beta_{b_{m-1}}\ldots \beta_{b_0})_3\tag{2}$$ Thus, all that remains is to determine $B(n)$, then we have solved the problem.

From substituting $g(n) = n$, we have that: $$A(n) - B(n) + D(n) = n$$

Thus: $$\begin{align} B(n) &= \underbrace{A(n) + \color{red}{C(n)} + D(n)}_{\text{simplify using $(2)$}} \color{red}{- C(n)} - n\\ &= \underbrace{(1\ldots1)_3}_{m+1 \text{ digits}} - C(n) -n \\ &= \frac{3^{m+1}-1}{2} - \left(\sum_{{k,\text{ where } b_k = 0}} 3^k\right) - n \end{align}$$

This leads us to the solution: $$g(n) = (\alpha\beta_{b_{m-1}}\ldots \beta_{b_0})_3 + \gamma\left(\frac{3^{m+1}-1}{2} - \left(\sum_{{k,\text{ where } b_k = 0}} 3^k\right) - n\right)$$ ...where $n=(b_mb_{m-1}\ldots b_0)_2$.

I'd like to get the sum out of the solution, but I don't know of a good way to do so. (I doubt if it is possible.)

$\endgroup$
3
  • $\begingroup$ You need two things for a solution without a sum. Use of the parameter change $(\alpha, \gamma,\beta_0,\beta_1) \to (0,0,0,1)$ and acceptance of the general radix changing solution as a closed form. See my answer. Also, there are a few notational errors in your solution. Equation (2) has inconsistent use of $\beta$ versus $b$ and I believe the first part of your final solution should read $(αβ_{b_{m−1}}...β_{b_{1}}β_{b_{0}})_3$. $\endgroup$
    – tmastny
    Dec 26 '14 at 1:33
  • 1
    $\begingroup$ @tmastny Thanks for the input; I'll have to wait until after break to respond, though--my copy of Concrete Math is at school. :) $\endgroup$
    – apnorton
    Dec 26 '14 at 3:12
  • $\begingroup$ @tmastny Ok, I've just edited to fix the problems you've brought up in the comments... (better late than never, right?) :) $\endgroup$
    – apnorton
    Jan 30 '15 at 23:15
1
$\begingroup$

Concrete Mathematics, Problem 1.16

\[ g(1)=\alpha \] \[ g(2n+j)=3g(n)+\gamma n+\beta_j \] \[ \mbox{for}\ j=0,1\ \mbox{and}\ n\geq1 \]

Solution

First let's take note of all of the applicable ways to describe $n$ \[ n=2^m+l=(1b_{m-1}b_{m-2}...b_1b_0)_2 \]

We can also define $g(n)$ as a linear combination of unknown functions of $n$ and their corresponding coefficients \[ g(n)=a(n)\alpha + b(n)\beta_0 + c(n)\beta_1 + d(n)\gamma \]

The next step is to manually calculate $g(n)$, for the first few values of $n$, in an attempt to find a pattern. After observing the output of $g(n)$, we can easily see that $a(n)$ is a power of $3$. This observation hints at analyzing the output of $g(n)$ in base $3$

\[ \begin{array}{c|c|c|c|c|c|c} n & n_2 & a(n)_3 & b(n)_3 & c(n)_3 & d(n)_3 \\ \hline 1 & 1 & 1 & 0 & 0 & 0 \\ \hline 2 & 1\color{red}{0} & 10 & \color{red}{1} & 0 & 1 \\ 3 & 1\color{green}{1} & 10 & 0 & \color{green}{1} & 1 \\ \hline 4 & 1\color{red}{00} & 100 & \color{red}{11} & 0 & 12 \\ 5 & 1\color{red}{0}\color{green}{1} & 100 & \color{red}{10} & \color{green}{1} & 12 \\ 6 & 1\color{green}{1}\color{red}{0} & 100 & \color{red}{1} & \color{green}{10} & 20 \\ 7 & 1\color{green}{11} & 100 & 0 & \color{green}{11} & 20 \\ \hline 8 & 1\color{red}{000} & 1000 & \color{red}{111} & 0 & 201 \\ \end{array} \]

We can quickly find $a(n)$ with the repertoire method and an educated guess of $3^m$. Note that this guess is inspired by observing the output of $g(n)$ \[ \mbox{Let}\ g(n)=g(2^m+l)=3^m \] \[ \mbox{Then}\ g(1)=g(2^0+0)=3^0=1=\alpha \] \[ g(2n+j)=g(2^{m+1}+2l+j)=3(3^m)+\gamma n+\beta_j\] \[ 3^{m+1}= 3^{m+1}+\gamma n +\beta_j\] Which implies that \[ 0= \gamma n+\beta_j \] \[ \alpha=1, \beta_0=0, \beta_1=0, \gamma=0 \] \[ 3^m =1a(n) + 0b(n) + 0c(n) + 0d(n) \] Thus \[ a(n) = a(2^m + l) = 3^m \]

In order to find $b(n)$, we must notice that for every binary bit $b_x$ in $n$, where $x < m$ and $b_x=0$, there is a ternary digit $1$ in the output of $b(n)$ at position $x$. This relationship is expressed in the above table in red and with a bit of set builder notation below. Note that $0\in\mathbb{N}$, as it's quite natural to have nothing \[ b(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=0)\} \]

Interestingly enough, finding $c(n)$ is similar with the exception that $b_x=1$. This is also expressed in the above table in green and below as follows \[ c(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\} \]

After defining $a(n)$, $b(n)$ and $c(n)$, the following equation becomes almost trivial \[ a(n)\alpha + b(n)\beta_0 + c(n)\beta_1 = (\alpha\beta_{b_{m-1}}\beta_{b_{m-2}}...\beta_{b_1}\beta_{b_0})_3 \]

Now we can find $d(n)$ with the repertoire method and a standard guess of $n$ \[ \mbox{Let}\ g(n)=n \] \[ \mbox{Then}\ g(1)=1=\alpha \] \[ g(2n+j)=3n+\gamma n+\beta_j\] \[ 2n+j= 3n+\gamma n +\beta_j\] Which implies that \[ -n+j= \gamma n+\beta_j \] \[ \alpha=1, \beta_0=0, \beta_1=1, \gamma=-1 \] \[ n =1a(n) + 0b(n) + 1c(n) - 1d(n) \] Thus \[ d(n) = a(n)+c(n)-n \]

So now we have the solutions \[ a(n) = 3^m \] \[ b(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=0)\} \] \[ c(n)=\sum \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\} \] \[ d(n) = a(n)+c(n)-n \]

Here's a brief example of how to calculate $a(n)$, $b(n)$, $c(n)$ and $d(n)$ \[ \mbox{Let}\ n=19=2^4+3=(10011)_2\] \[ a(19)=3^4=81=(10000)_3 \] \[ b(19)=3^2+3^3=36=(1100)_3 \] \[ c(19)=3^0+3^1=4=(11)_3 \] \[ d(19)=81+4-19=66=(2110)_3 \]

This is good but, we can do better. Lets simplify this solution by finding another equation via the repertoire method \[ \mbox{Let}\ g(n)=1 \] \[ \mbox{Then}\ g(1)=1=\alpha \] \[ g(2n+j)=3(1)+\gamma n+\beta_j\] \[ 1= 3+\gamma n +\beta_j\] Which implies that \[ -2= \gamma n+\beta_j \] \[ \alpha=1, \beta_0=-2, \beta_1=-2, \gamma=0 \] \[ 1 =1a(n) -2b(n) -2c(n) +0d(n) \] Thus \[ b(n) = \frac{1}{2}(a(n)-1)-c(n) \]

Now we can express $b(n)$ in terms of $a(n)$ and $c(n)$, thus eliminating the summation. So let's put everything together \[ g(n)=a(n)\alpha + (\frac{1}{2}a(n)-\frac{1}{2}-c(n))\beta_0 + c(n)\beta_1 + (a(n)+c(n)-n)\gamma \] \[ g(n)=a(n)\alpha + \frac{1}{2}a(n)\beta_0-\frac{1}{2}\beta_0-c(n)\beta_0 + c(n)\beta_1 + a(n)\gamma+c(n)\gamma-n\gamma \] \[ g(n)=a(n)(\alpha + \frac{1}{2}\beta_0+\gamma)+ c(n)(\beta_1 -\beta_0+\gamma)-n\gamma -\frac{1}{2}\beta_0 \]

Therefore, the closed form solution is \[ \mbox{Let}\ S= \{3^x : (\exists x)(x\in\mathbb{N}, x < m, b_x=1)\} \] \[ g(n)=3^m(\alpha + \frac{1}{2}\beta_0+\gamma)+ (\beta_1 -\beta_0+\gamma) \sum S- n\gamma -\frac{1}{2}\beta_0 \] I hope this helps you understand.

$\endgroup$
5
  • $\begingroup$ This is wrong. Note $g(2) = 3\alpha + \beta_0 + \gamma$. However, using your function, $g(2) = g(2^1 + 0) = 3\alpha + \beta_1 + 2\gamma$. $\endgroup$
    – tmastny
    Dec 26 '14 at 2:06
  • 1
    $\begingroup$ @tmastny, I beg to differ. Note that the value of an empty sum is zero. Therefore, $$g(2)=3(\alpha+\frac12 \beta_0 + \gamma)+(\beta_1 - \beta_0 +\gamma) 0 - 2\gamma -\frac12 \beta_0=3\alpha +\beta_0 + \gamma$$ $\endgroup$
    – k170
    Dec 26 '14 at 2:34
  • 1
    $\begingroup$ @tmastny, if you'd like to understand why the sum is zero, lets look at the members of the set $S$ when $n=2$. Since $n=2^m+l$, then $n=2^1+0=2$ implies that $m=1$. Also note that the binary equivalent of $2$ is $10_2$ and the binary bit $b_0 \not = 1$, therefore the set $S$ has zero members when $n=2$. Since $S=\varnothing$, then $\sum \varnothing = 0$. Merry Christmas =). $\endgroup$
    – k170
    Dec 26 '14 at 3:06
  • $\begingroup$ Cool thanks, I get it now. $\sum S$ is converting radix-2 into radix-3 by keeping the coefficients and turning the powers into powers of 3 (dropping the most significant bit). Looking back at the chart helped. $\endgroup$
    – tmastny
    Dec 26 '14 at 4:37
  • 1
    $\begingroup$ @tmastny, anytime. Glad I could help. $\endgroup$
    – k170
    Dec 26 '14 at 5:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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