# 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

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

Applying the *repertoire method* for the declared goal, we plug in simple
functions of `n`

into the general form of the solution:

**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.