# Repertoire method for solving recursions

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

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

• 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. Jan 30 '15 at 23:23
• 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). Jan 31 '15 at 0:15

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

• 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$. Dec 26 '14 at 1:33
• @tmastny Thanks for the input; I'll have to wait until after break to respond, though--my copy of Concrete Math is at school. :) Dec 26 '14 at 3:12
• @tmastny Ok, I've just edited to fix the problems you've brought up in the comments... (better late than never, right?) :) Jan 30 '15 at 23:15

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.

• 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$. Dec 26 '14 at 2:06
• @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$$
– k170
Dec 26 '14 at 2:34
• @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 =).
– k170
Dec 26 '14 at 3:06
• 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. Dec 26 '14 at 4:37
• @tmastny, anytime. Glad I could help.
– k170
Dec 26 '14 at 5:03