As with most of my posts on Concrete Mathematics this is a more verbose outline of the repertoire method in section 2.2. It explains how to find the closed form to the sum recurrence 2.7 which I reproduce here

R0=αRn=Rn1+β+γn

Then, as in chapter one, we work through a few small cases like R1=α+β+γ, R2=α+2β+3γ and so on. We can see that there is α, β, γ (the “general parameters”) which have “something done” to them to give us the final closed form. This “something we do” is represented by, at this point, unknown functions A(n), B(n), and C(n) (a.k.a. coefficients of dependence on the before mentioned general parameters). Putting them together we have a framework for starting to find our closed form

Rn=A(n)α+B(n)β+C(n)γ

What the book does is cleverly plug in “simple functions of n for Rn” and letting the right-hand-side shake itself out. With some luck we’ll just have one of α, β, or γ left equalling the “simple function of n”. Let’s put it to action

Finding A(n)Permalink

Here they set Rn=1 and, lo and behold, the general parameters end up as α=1, β=0, γ=0. Now, why this is confused me (I could still be confused but not know it), until I pondered the logical implications of setting Rn=1. NOTE it is not the same as setting n=1; for this repertoire item the whole sum is 1

So if the whole sum is 1 what does that mean? Using the recurrence it must mean that Sn1 is 1, β is 0, and γ is 0. If β and γ were anything other than zero then the sum would not be 1. Hence α=1

Now, using that info, we can sub-in α=1, β=0, γ=0 to the closed form

1=A(n)1+B(n)0+C(n)01=A(n)

Finding B(n)Permalink

With similar logic to above, setting Rn=n, it means the whole sum is the same as n. The only way that could be is if we’re simply adding 1 with each recurrence iteration. So it would be like a recurrence of Rn=Sn1+1+0(n) meaning α=0 (the first iteration would be 0) and γ=0 otherwise we’d have a result of Rn>n. Hence α=0, β=1, γ=0. Plugging in those values to our proposed closed form we get

n=A(n)0+B(n)1+C(n)0n=B(n)

Finding C(n)Permalink

This one I didn’t figure out without some help from Professor Internet in the form of Hans Lundmark in a comment. For this particular repertoire item the authors are setting Rn to n2. With that done it implies α=0 because 02=α. To then see what β and γ need to be in order to eliminate them we simply plug in n2 to the recurrence RHS so

n2=(n1)2+β+γnn2=n22n+1+β+γn

At this point we do some selective factoring in order to see what β and γ need to be set to in order to get our simple repertoire item for C(n). First re-arrange to make it more obvious (swap β and γ)

n2=n22n+γn+1+βn2=n2+n(γ2)+1(1+β)

And, tada, we can see we need to set γ=2 and β to 1. Using this info we can plug it back into our proposed closed form:

n2=A(n)0+B(n)1+C(n)2n2=0B(n)+2C(n)n2=2C(n)B(n)

At this point we know B(n)=n (from previous repertoire step for B(n)) so sub that in and rearrange to get the result

n2=2C(n)nn2+n=2C(n)n2+n2=C(n)

Tie it all togetherPermalink

So the final closed form ends up being

Rn=α+nβ+(n2+n2)γ

But, wait, there’s more! The sum recurrence of the form (2.6 in book)

S0=a0Sn=Sn1+an

Looks like this in the general sum-recurrence form

R0=αRn=Rn1+β+γn

Which, in turn, looks like this in summation form

k=0n(a+bk)

Now, in the case of 2.7, we see that α=β=a and γ=b. So our closed form can be simplified in the following way

aA(n)+aB(n)+bC(n)=a1+an+b(n2+n2)=a(n+1)+b(n+1)n/2

Because we can plug in the known values for A(n), B(n), and C(n)