Repertoire Method for Solving Recurrences

Using constants, we can try to find a closed form formula for recurrences. This method starts with a “repertoire” of simple known functions and determines which recurrences they satisfy.

These recurrences define J:

$$ \begin{aligned} J\left(1\right) &= 1 \\ J\left(2n\right) &= 2J\left(n\right)-1, for\ n \ge 1 \\ J\left(2n+1\right) &= 2J\left(n\right)+1, for\ n \ge 1 \\ J\left(2^m+l\right) &= 2l + 1,\ for\ m \ge 0\ and\ 0 \le l \lt 2^m \end{aligned} $$

Here is J aliased as f with our constants:

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

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

The repertoire method allows us to swap coefficients of the constants with simple functions:

The table shows that the coefficient of \( \alpha \) is the largest power of 2 in n. Between powers of 2, the \( \beta \) coefficient decreases by 1 down to 0 and \( \gamma \) increases by 1 up from 0. This behavior can be expressed as functions A(n) for the largest power of 2 in n, B(n) for the coefficient that decreases from that power of 2 down to 0, and C(n) for the coefficient that increases by 1 up from 0. $$ \begin{aligned} f\left(n\right) &= A\left(n\right)\alpha + B\left(n\right)\beta + C\left(n\right)\gamma \\ \end{aligned} $$

Let \( \alpha = 1, \beta = \gamma = 0 \), for \(f\left(n\right) = A\left(n\right)\):

$$ \begin{aligned} A\left(n\right) &= 1 \\ A\left(2n\right) &= 2A\left(n\right),\ for\ n \ge 1 \\ A\left(2n+1\right) &= 2A\left(n\right),\ for\ n \ge 1 \\ A\left(2^m+l\right) &= 2^m,\ for\ m \ge 0\ and\ 0 \le l \lt 2^m \end{aligned} $$ Therefore: \( A\left(n\right) = 2^m \).

Let \( \alpha = 1, \beta = -1, \gamma = -1 \), for \(f\left(n\right)=1\):

Substituting into the recurrence gives \(f(n) = 1\) for all \(n\), so: $$ \begin{aligned} f\left(n\right) &= A\left(n\right) \cdot 1 + B\left(n\right) \cdot (-1) + C\left(n\right) \cdot (-1) = 1 \\ A\left(n\right) - B\left(n\right) - C\left(n\right) &= 1 \end{aligned} $$ Rearranging gives us a formula for \(B\left(n\right)\): $$ B\left(n\right) = A\left(n\right) - 1 - C\left(n\right) = 2^m - 1 - l $$

Let \(\alpha = 1, \beta = 0, \gamma = 1\), for \(f\left(n\right)=n\):

Substituting into the recurrence gives \(f(n) = n\) for all \(n\): $$ \begin{aligned} f\left(1\right) &= 1 = \alpha \\ f\left(2n\right) &= 2n = 2n + \beta \\ f\left(2n+1\right) &= 2n+1 = 2n + \gamma \end{aligned} $$ So \(f(n) = A\left(n\right) \cdot 1 + B\left(n\right) \cdot 0 + C\left(n\right) \cdot 1 = n\), therefore: $$ \begin{aligned} A\left(n\right) + C\left(n\right) &= n \\ C\left(n\right) &= n - A\left(n\right) = l \end{aligned} $$

Our simple functions:

$$ \begin{aligned} A\left(n\right) &= 2^m,\ where\ n = 2^m + l\ and\ 0 \le l \lt 2^m \\ A\left(n\right) - B\left(n\right) - C\left(n\right) &= 1 \\ A\left(n\right) + C\left(n\right) &= n \\ B\left(n\right) &= A\left(n\right) - 1 - C\left(n\right) = 2^m - 1 - l \\ C\left(n\right) &= n - A\left(n\right) = l \end{aligned} $$

Substituting back into \( f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma \), we get our closed form: $$ f\left(n\right) = 2^m \alpha + \left(2^m - 1 - l\right)\beta + l\gamma $$

To recover \( J(n) \), we match the original recurrence where \( \alpha = 1,\ \beta = -1,\ \gamma = 1 \): $$ \begin{aligned} J\left(n\right) &= 2^m \cdot 1 + \left(2^m - 1 - l\right) \cdot (-1) + l \cdot 1 \\ &= 2^m - 2^m + 1 + l + l \\ &= 2l + 1 \end{aligned} $$

This confirms our closed form solution: $$ \boxed{J\left(2^m + l\right) = 2l + 1,\ for \quad m \ge 0,\ 0 \le l \lt 2^m} $$