Repertoire method for solving recursions

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.