This method is an important method that appears in the textbook for CSE547 ¹ of solving recurences with constant parameters.

Repertoire method assumes that the final result can be expressed by the linear combination of the constant parameters of the recurence, where the coefficients only depend on $n$.

Assume the parameters of some recurence is {$\alpha, \beta,\gamma$}, we want to assume $f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma$ (we should first try several cases and check whether they satisfy this kind of form). Since this fomula should hold for arbitrary $\alpha, \beta, \gamma$, what we need to do is to find some special cases of {$\alpha, \beta,\gamma$} and solve the recurence under these special cases of parameters. Then we will get some equations for $A(n), B(n), C(n)$.

Example 1

$$ \begin{cases} f(j) = \alpha_j, for\ \ 1 \le j < d\cr f(dn + j) = cf(n) + \beta_j,\ \ for\ \ 0 \le j < d\ \ and\ \ n \ge 1 \end{cases} $$

We assume that $$f(n) = \sum_j A_j(n)\alpha_j + \sum_j B_j(n)\beta_j.$$

case 1

For some $k$, $\alpha_k = 1$. Other parameters equal to zero.

So $f(n) = A_k(n)$.

On the other hand, $f(k) = 1$, $f(dk + b_1) = c f(k) = c$, $f(d(dk+b_1) + b_2) = f(k d^2 + b_1d + b_2) = cf(dk + b_1) = c^2 $.

By induction, we will get $f({(kb_1b_2b_3…b_n)}_d) = c^n$.

In the same way, if $j \not= k$, we will get $$ f({(jb_1b_2b_3…b_n)}_d) = 0, j \not = k$$

Finally, we get $$A_k({(b_0b_1b_2b_3…b_n)}_d) = [b_0 = k]c^n$$

case 2

For some $k$, $\beta_k = 1$, other parameters equal to zero.

So $B_k(n) = f(n)$.

On the other hand, $f(b_0) = 0$, $f(jd + b_1) = [b_1 = k]$, $f(d(kd + b_1) + b_2) = f(kd^2 + b_1d + b_2)$ $=[b_1 = k] c + [b_2 = k]$

By induction, we can get $$f({(b_0b_1b_2b_3…b_n)}_d) = [b_1 = k]c^{n-1} + … + [b_n = k]c^0. $$

So $$ B_k({(b_0b_1b_2b_3…b_n)}_d) = [b_1 = k]c^{n-1} + … + [b_n = k]c^0. $$

general case

Given an input of form $n = (b_0b_1b_2…b_n)_d$, we know that $f(n)$ is a linear combination of {${c^n, c^{n-1}, …, c^0}$}.

When $j > 0$, $c^{n-j}$’s coefficient $c_j$ has the form: $$c_j = \sum _{i=1} ^n\beta_i[b_j = i] = \beta _{b_j}.$$

When $j = 0$, $c^n$’s coefficient $c_0$ has the form: $$c_n = \sum _{i=1} ^n\alpha_i[b_0 = i] = \alpha _{b_0}.$$

Combine them, then we get $$f({(b_0b_1b_2b_3…b_n)}_d) = (\alpha _{b_0}\beta _{b _{1}}\beta _{b _{2}}…\beta _{b_n})$$

Example 2: Sum of polynomials.

$$ \begin{cases} S_0 = \alpha,\cr S_n = S _{n-1} + \sum _{i = 0}^{k}a_kn^k \end{cases} $$ Again, we assume $$S(n) = A(n)\alpha + \sum _{i = 0} ^k A_i(n) a_i$$

Try as follows:

1. $\alpha = 1$, other parameters equal to 0. $S_n = \alpha = 1 = A(n)$.

2. For some $k$, $a_k = 1$, other parameters equal to zero. $S_n = \sum _{i=1} ^n i^k = A_i(n)$. It seems that this is useless.

To get some useful special cases of parameters, we can set a special sequence and then compute the parameters for that.

For example,

1. Let f(n) = 1. We already know that in this case, $\alpha = 1$, and other parameters equal to 0. So, $$ 1 = A(n)$$

2. Let f(n) = n. We will get $\alpha = 0$, $a_0 = 1$, other parameters equal to zero, and following equation: $$n = A_0(n)$$

3. Let f(n) = n^2. We will get $\alpha = 0$, $a_0 = -1, a_1 = 2$, and other parameters equal to zero. So we have: $$ n^2 = 2A_1(n) - A_0(n)$$

In the same way, increase the power to $n$, we will get $n$ equations in the form as follows: $$ n^k = - \sum_{i = 0} ^ {k-1}(-1)^{k-i} \binom{k}{i}A_i(n)$$ where $k \ge 1$ And plus $1 = A(n), we can solve all coefficients of parameters.

Furthermore, we know that $A_k(n) = \sum _{i = 0} ^{n} i^k$, so we find a way to compute this: $$ A_k(n) = \frac{n^{k+1} + \sum _{i=0}^{k-1}(-1)^{k-i}\binom{k}{i}A_i(n)}{k}.$$