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
Then, as in chapter one, we work through a few small cases like , 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 , , and (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
What the book does is cleverly plug in “simple functions of n for ” 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
Here they set and, lo and behold, the general parameters end up as , , .
Now, why this is confused me (I could still be confused but not know it), until I pondered the logical implications of
setting . NOTE it is not the same as setting ; for this repertoire item the whole sum is 1
So if the whole sum is what does that mean? Using the recurrence it must mean that is , is ,
and is . If and were anything other than zero then the sum would not be . Hence
Now, using that info, we can sub-in , , to the closed form
Finding
With similar logic to above, setting , it means the whole sum is the same as . The only way that could be is
if we’re simply adding with each recurrence iteration. So it would be like a recurrence of meaning (the first iteration would be 0) and otherwise we’d have a result of .
Hence , , . Plugging in those values to our proposed closed form we get
Finding
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 to . With that done it implies because . To then see what and need to be in order to eliminate them we simply plug in
to the recurrence RHS so
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 . First re-arrange to make it more obvious (swap and
)
And, tada, we can see we need to set and to . Using this info we can plug it back into our
proposed closed form:
At this point we know (from previous repertoire step for ) so sub that in and rearrange to get the result
Tie it all together
So the final closed form ends up being
But, wait, there’s more! The sum recurrence of the form (2.6 in book)
Looks like this in the general sum-recurrence form
Which, in turn, looks like this in summation form
Now, in the case of 2.7, we see that and . So our closed form
can be simplified in the following way
Because we can plug in the known values for , , and