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

$\begin{equation*} \sum_{k=0}^n(x + yk) \ , \end{equation*}$ 1

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

$\begin{equation*} \flushleft R_0 = \alpha \ ; \\ R_n = R_{n - 1} + \beta + \gamma n \ , \quad \text{for } n > 0 \ . \end{equation*}$ 2

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

$\begin{equation*} R_n = A(n) \times \alpha + B(n) \times \beta + C(n) \times \gamma \ . \end{equation*}$ 3

First simple function we plug in is $R_n = 1$ .

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

$\begin{equation*} R_0 = \alpha = 1 \end{equation*}$

and

$\begin{align*} R_n &= R_{n - 1} + \beta + \gamma n \\ &= 1 + \beta + \gamma n = 1 \ . \end{align*}$

Hence

$\begin{equation*} \beta + \gamma n = 0 \ , \end{equation*}$

so $\beta = 0$ and $\gamma = 0$ .

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

$\begin{align*} R_n &= A(n) \times 1 + B(n) \times 0 + C(n) \times 0 \\ &= A(n) = 1 \ . \end{align*}$

So, we've figured the value of one of the coefficients, $A(n) = 1$ .

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

$\begin{equation*} R_0 = \alpha = 0 \end{equation*}$

and

$\begin{align*} R_n &= R_{n - 1} + \beta + \gamma n \\ &= n - 1 + \beta + \gamma n = n \ . \end{align*}$

It follows that

$\begin{equation*} \beta + \gamma n = 1 \ , \end{equation*}$

so $\beta = 1$ and $\gamma = 0$ .

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

$\begin{align*} R_n &= A(n) \times 0 + B(n) \times 1 + C(n) \times 0 \\ &= B(n) = n \ . \end{align*}$

The last, third function to plug in is $R_n = n^2$ .

With it, we get

$\begin{equation*} R_0 = \alpha = 0^2 = 0 \end{equation*}$

and

$\begin{align*} R_n &= R_{n - 1} + \beta + \gamma n \\ &= (n - 1)^2 + \beta + \gamma n \\ &= n^2 - 2n + 1 + \beta + \gamma n \\ &= 1 + \beta + \gamma n - 2n + n^2 = n^2 \ . \end{align*}$

Therefore,

$\begin{equation*} (1 + \beta) + n(\gamma - 2) = 0 \ . \end{equation*}$

This equation says us that $\beta = -1$ and $\gamma = 2$ .

By substitution,

$\begin{align*} R_n &= A(n) \times 0 + B(n) \times -1 + C(n) \times 2 \\ &= 2C(n) - B(n) = n^2 \ . \end{align*}$

Now we know that

$\begin{align*} C(n) &= \frac{n^2 + B(n)}{2} \\ &= \frac{n^2 + n}{2} \ . \end{align*}$

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

$\begin{align*} A(n) &= 1 \ ; \\ B(n) &= n \ ; \\ C(n) &= \frac{n^2 + n}{2} \ . \end{align*}$

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

$\begin{align*} x &= \alpha = \beta \ ; \\ &y = \gamma \ . \end{align*}$

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

$\begin{align*} R_n &= 1 \times x + n \times x + \frac{n^2 + n}{2} \times y \\ &= x(n + 1) + \frac{y(n^2 + n)}{2} \ . \end{align*}$

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

We continue demystifying Concrete Mathematics in the next post.