1

After attempting question 1.16 of Concrete Mathematics,

$g(1)=\alpha$

$g(2n+j)=3g(n)+\gamma n+ \beta_j, j=0,1$

I am having some difficulty getting the correct answer.

The following is my working:

$ g(n)=A(n)\alpha + B_0(n)\beta_0 + B_1(n)\beta_1 + C(n)\gamma$

Using $\alpha =1$ and $\beta_0,\beta_1,\gamma=0$

I get $A(2^m+l)=3^m$

Using $g(n)=1$

I get $g(n)=A(n)-2B_0(n)-2B_1(n)=1$

Using $g(n)=n$

I get $g(n)=A(n)+B_1(n)-C(n)=n$

Using $g(n)=n^2$

I get $g(n)=A(n)-2B_0(n)+3B_1(n)+3C(n)=n^2$

However, with these 4 equations I am unable to get an answer that tallies with the values n=5 of the recurrence, i.e. $g(5)=9α+3β0+β1+5γ$

switch
  • 11
  • I agree with your equations. When I solve for $B_0(n),B_1(n)$, and $C(n)$ in terms of $A(n)$ I get $$\left{\begin{align} B_0(n)&=\frac18\left(7A(n)-n^2-3n-3\right)\ B_1(n)&=\frac18\left(-3A(n)+n^2+3n-1\right)\ C(n)&=\frac18\left(5A(n)+n^2-5n-1\right);. \end{align}\right.$$ – Brian M. Scott May 12 '20 at 22:52
  • I do get the same solution, but it does not tally with the values of $n=5$,

    i.e. $g(5)=9\alpha + 3\beta_0 + \beta_1 + 5\gamma$

     – switch May 13 '20 at 04:15
  • The error is in $g(n)=n^2$, which we don’t actually need, but it’s very late here, and I don’t have time to try to sort it out tonight. – Brian M. Scott May 13 '20 at 05:47
  • Sure, if you happen to have time could you explain to me why $g(n)=n^2$ can't be used? Thanks! – switch May 13 '20 at 10:55
  • You’re welcome. I’ve added an answer with a brief explanation and a pointer to an old answer of mine that discussed this very problem in some detail. – Brian M. Scott May 13 '20 at 16:11

1 Answers1

1

We don’t actually need $g(n)=n^2$, and it’s where the calculation goes wrong. The problem with it is that $g(n)=n^2$ simply isn’t consistent with the recurrence: there is no choice of $\alpha,\beta_0,\beta_1$, and $\gamma$ that generates it. Specifically, the ones that work for $n\le 4$ fail at $n=5$.

However, we can get $A,B_0$, and $B_1$ directly from formula $(1.18)$ in the text. I’d forgotten, but it turns out that I actually explained that some years ago in answer to another question. The nature of $(1.18)$ means that the definitions of $B_0,B_1$, and $C$ are a bit ugly, since they’re expressed directly in terms of the binary representation of $n$, but they’re not bad to work with in practice.

Brian M. Scott
  • 616,228
  • Thanks! I can understand the solution to the problem, but could you re-explain the $g(n)=n^2$ part again, I don't quite get it. Why is it not consistent with the recurrence, and why can $g(n)=n$ be used but not $g(n)=n^2$ – switch May 14 '20 at 17:32
  • @Switch: I’ve not actually thought about the underlying reason that $g(n)=n^2$ can’t be used, but the fact itself is clear: when we try to use it and calculate $\alpha,\beta_0,\beta_1$, and $\gamma$, we find that the only values that work for $n\le 4$ fail for $n=5$. This shows that there are no values that generate the squaring function: it’s simply not one of the functions satisfying the recurrence. With $g(n)=n$, however, we can find values that work for all $n$. I don’t have time, but it might be illuminating to look at Problem 1.20, in which $g(n)=n^2$ does satisfy a somewhat ... – Brian M. Scott May 14 '20 at 17:42
  • ... similar recurrence, to see whether you can see why having different $\gamma n$ terms in the even and odd cases makes a difference. – Brian M. Scott May 14 '20 at 17:44