Mathematics · Recurrences · Repertoire Method

Repertoire Method for Solving Recurrences

The repertoire method starts with a family of simple functions, studies which recurrence each one satisfies, and then combines those functions to recover a closed form for the target recurrence.

Main idea

Start with a generic recurrence containing constants, then solve for the coefficient functions attached to those constants.

Three helper functions

\(A(n)\), \(B(n)\), and \(C(n)\) track how the coefficients of \(\alpha\), \(\beta\), and \(\gamma\) behave.

Final result

\(J(2^m+l)=2l+1\) for \(m\ge 0\) and \(0\le l<2^m\).

Introduction

Using constants, we can search for a closed-form formula for a recurrence by building a small repertoire of functions whose behavior we already understand.

Instead of solving the target recurrence in one leap, the repertoire method breaks the job into easier pieces. Each constant in a generalized recurrence gets paired with a coefficient function, and those coefficient functions are solved one at a time.

Core strategy First generalize the recurrence, then solve the coefficient functions, then plug the original constants back in.

Target recurrence

The Recurrence Defining \(J\)

$$ \begin{aligned} J(1) &= 1, \\ J(2n) &= 2J(n)-1, \qquad n \ge 1, \\ J(2n+1) &= 2J(n)+1, \qquad n \ge 1, \\ J(2^m+l) &= 2l+1, \qquad m \ge 0,\; 0 \le l < 2^m. \end{aligned} $$

The goal is to recover the final closed form from the recurrence itself, rather than simply accept it as given.

Generalized form

Alias \(J\) as a More Flexible Function

Replace the specific constants with parameters \(\alpha\), \(\beta\), and \(\gamma\):

$$ \begin{aligned} f(1) &= \alpha, \\ f(2n) &= 2f(n)+\beta, \qquad n \ge 1, \\ f(2n+1) &= 2f(n)+\gamma, \qquad n \ge 1. \end{aligned} $$

Now the recurrence describes an entire family of functions instead of just one.

\(n\)	\(f(n)\)
1	\(\alpha\)
2	\(2\alpha+\beta\)
3	\(2\alpha+\gamma\)
4	\(4\alpha+3\beta\)
5	\(4\alpha+2\beta+\gamma\)
6	\(4\alpha+\beta+2\gamma\)
7	\(4\alpha+3\gamma\)
8	\(8\alpha+7\beta\)
9	\(8\alpha+6\beta+\gamma\)

The table suggests that the coefficients of \(\alpha\), \(\beta\), and \(\gamma\) each follow their own recognizable pattern.

Coefficient functions

Introduce \(A(n)\), \(B(n)\), and \(C(n)\)

The repertoire method packages those coefficient patterns into three simple functions:

\[ f(n)=A(n)\alpha + B(n)\beta + C(n)\gamma. \]

From the table:

• \(A(n)\) behaves like the largest power of 2 not exceeding \(n\)
• \(B(n)\) decreases from that power of 2 down toward 0
• \(C(n)\) increases from 0 upward

Solve \(A(n)\)

Let \(\alpha=1\), \(\beta=0\), \(\gamma=0\)

Then \(f(n)=A(n)\), and the recurrence becomes:

$$ \begin{aligned} A(1) &= 1, \\ A(2n) &= 2A(n), \qquad n \ge 1, \\ A(2n+1) &= 2A(n), \qquad n \ge 1. \end{aligned} $$

If \(n=2^m+l\) with \(0\le l<2^m\), then:

\[ A(n)=2^m. \]

So \(A(n)\) is exactly the largest power of 2 not exceeding \(n\).

Solve \(C(n)\)

Let \(\alpha=1\), \(\beta=0\), \(\gamma=1\)

With this choice, the recurrence becomes \(f(n)=n\):

$$ \begin{aligned} f(1) &= 1, \\ f(2n) &= 2n, \\ f(2n+1) &= 2n+1. \end{aligned} $$

Since \[ f(n)=A(n)\cdot 1 + B(n)\cdot 0 + C(n)\cdot 1, \] we get:

\[ A(n)+C(n)=n. \]

Therefore:

\[ C(n)=n-A(n)=l. \]

Solve \(B(n)\)

Let \(\alpha=1\), \(\beta=-1\), \(\gamma=-1\)

With this choice, the recurrence becomes \(f(n)=1\) for all \(n\). So:

\[ A(n)-B(n)-C(n)=1. \]

Rearranging gives:

\[ B(n)=A(n)-1-C(n). \]

Substituting the earlier formulas for \(A(n)\) and \(C(n)\):

\[ B(n)=2^m-1-l. \]

Assemble the general solution

Combine the Three Coefficient Functions

We now have:

$$ \begin{aligned} A(n) &= 2^m, \\ C(n) &= l, \\ B(n) &= 2^m - 1 - l, \end{aligned} \qquad \text{where } n=2^m+l,\; 0\le l<2^m. $$

Substitute back into \[ f(n)=A(n)\alpha + B(n)\beta + C(n)\gamma \] to get:

\[ f(n)=2^m\alpha + (2^m-1-l)\beta + l\gamma. \]

Recover \(J(n)\)

Plug the Original Constants Back In

For the original recurrence \(J(n)\), the constants are:

\[ \alpha=1,\qquad \beta=-1,\qquad \gamma=1. \]

So:

$$ \begin{aligned} J(n) &= 2^m(1) + (2^m-1-l)(-1) + l(1) \\ &= 2^m - 2^m + 1 + l + l \\ &= 2l+1. \end{aligned} $$

Closed form \[ J(2^m+l)=2l+1, \qquad m\ge 0,\; 0\le l<2^m. \]

FAQ

Frequently Asked Questions

These are the practical questions students usually have when first learning the repertoire method.

Why introduce \(\alpha\), \(\beta\), and \(\gamma\) instead of solving \(J(n)\) directly?

Because the generalized recurrence reveals reusable coefficient patterns. Once those are known, the original problem becomes a substitution exercise.

What is the role of \(A(n)\), \(B(n)\), and \(C(n)\)?

They track how the coefficients of the constants evolve through the recurrence, turning the problem into three simpler subproblems.

Why is \(A(n)\) the largest power of 2 not exceeding \(n\)?

Because both even and odd steps double the previous coefficient, so the coefficient changes only when crossing powers of 2.

Why does \(C(n)\) become \(l\)?

Once \(A(n)+C(n)=n\) and \(A(n)=2^m\), the leftover portion is exactly \(l\) in the decomposition \(n=2^m+l\).

Why does the final answer use \(n=2^m+l\)?

Because that decomposition separates the largest power of 2 from the remainder, which is exactly the structure the recurrence responds to.

What is the simplest takeaway from this method?

Generalize first, solve the coefficient functions second, and recover the original recurrence last.

Raell Dottin