RtW

15 April 2022

# Sums and Recurrences: Repertoire Method

With this post, we get to the second part (hurray!) of Concrete Mathematics, called Sums. The first chapter of this part is pretty simple, so doesn't seem to require any clarifications. But the second chapter has the potential to make us (non-mathematicians) feel lost and stupid. In this chapter we meet the repertoire method again. It was — in quite an obscure way – introduced earlier in the book. Now we're going to apply this method to evaluate a sum in its closed form, namely, the sum

1

which can be written in a form of a general recurrence relation

2

Applying the repertoire method for the declared goal, we plug in simple functions of n into the general form of the solution:

3

First simple function we plug in is .

In this case, by substitution into the recurrence (2),

and

Hence

so and .

Now, by substitution into the general solution (3),

So, we've figured the value of one of the coefficients, .

The second function to try out is . We perform the same substitutions as above. By substitution into (2), we get

and

It follows that

so and .

The substitution of the found parameters into (3) results in

The last, third function to plug in is .

With it, we get

and

Therefore,

This equation says us that and .

By substitution,

Now we know that

At this stage we have gathered all the parameters to substitute into (3):

For coefficients, we look at the sum (1) and its general recurrence (2):

By substitution of the coefficients and parameters into the general solution (3), we get

And this finalizes our investigation of the application of repertoire method for sum evaluation.

We continue demystifying Concrete Mathematics in the next post.