There are some existing questions on the repertoire method from the first chapter but I think I'm stuck on something different than the part people usually have trouble with.
I think the jump in the first chapter from 1.11 to 1.13 is unjustified. Up to this point in the chapter, we have been constructively proving that closed forms exist for various recurrences, but here the authors never formally prove that 1.11 can be written as 1.13.
Intuitively I can partly justify it to myself that given the equations of 1.11 any closed form will have to be a sum of alphas, betas, and gammas, and that since n is the only parameter to f that the coefficients of alpha, beta, and gamma must be functions of n. However it is not clear to me why (as the authors seem to assume) every possible f written in this form must have the same definitions for A, B, and C. I can believe that given specific values for alpha, beta, and gamma that we could find satisfying definitions for those functions, but it is not at all clear to me how it is guaranteed those definitions still be stable across all the possible constants we could choose. The rest of the repertoire method example seems to rely on this being the case, so I'm stuck.
Put another way, I think of 1.11 as a function that takes three constants (alpha, beta, and gamma) and returns a particular function, $f_{(\alpha,\beta,\gamma)}(n) = A_{(\alpha,\beta,\gamma)}(n)\alpha + B_{(\alpha,\beta,\gamma)}(n)\beta + C_{(\alpha,\beta,\gamma)}(n)\gamma$. It's not clear why all the As, Bs, and Cs have to be the same across all possible f's. Is there a reason or is it not required that the definitions be stable? Getting independent equations for A, B, and C relies on us picking different f's so I don't see how this couldn't be the case.
Best Answer
Suppose that for some $n\ge 1$ we have $f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma$. Don’t worry for a moment about whether $A(n),B(n)$, and $C(n)$ depend on anything other than $n$; take them simply as numbers. Then
$$\begin{align*} f(2n)&=2f(n)+\beta\\ &=2\big(A(n)\alpha+B(n)\beta+C(n)\gamma\big)+\beta\\ &=2A(n)\alpha+\big(2B(n)+1\big)\beta+2C(n)\gamma\;, \end{align*}$$
so if set $A(2n)=2A(n)$, $B(2n)=2B(n)+1$, and $C(2n)=2C(n)$, we’ll automatically get $f(2n)=A(2n)\alpha+B(2n)\beta+C(2n)\gamma$. Similarly,
$$\begin{align*} f(2n+1)&=2f(n)+\gamma\\ &=2\big(A(n)\alpha+B(n)\beta+C(n)\gamma\big)+\gamma\\ &=2A(n)\alpha+2B(n)\beta+\big(2C(n)+1)\gamma\;, \end{align*}$$
so if we set $A(2n+1)=2A(n)$, $B(2n+1)=2B(n)$, and $C(2n+1)=2C(n)+1$, we’ll automatically get $f(2n+1)=A(2n+1)\alpha+B(2n+1)\beta+C(2n+1)\gamma$. Thus, the functions $A(n),B(n)$, and $C(n)$ are completely defined by the recurrences
$$\begin{align*} A(2n)&=2A(n)\\ A(2n+1)&=2A(n)\\ B(2n)&=2B(n)+1\\ B(2n+1)&=2B(n)\\ C(2n)&=2C(n)\\ C(2n+1)&=2C(n)+1 \end{align*}$$
and the initial values $A(1)=1$ and $B(1)=C(1)=0$; they do not depend on $\alpha,\beta$, and $\gamma$.