f(2n) = 2 * f(n) + beta for all n greater than or equal to 1

f(2n + 1 ) = 2 * f(n) + gamma for all n greater than or equal to 1

to solve a recurrence using the repertoire method ,

**step 1**

make sure that the recurence is expressible as a sum of parameters multplied by functions of n the above recurrence can be transforemd to f(n) = A(n)*alpha + B(n)*beta +C(n)* gamma (this is done on page 13 of the book so i don't repeat it here) where A, B and C are functions on n and alpha beta and gamma are constants

**step 2**

p times , where p is the number of parameters (in the above case, alpha, beta and gamma so p = 3 ) *assume* that f(n) = a simple function of n and solve using the original recurrence to get an equation . eg: in the above recurrence there are three parameters , alpha , beta and gamma so say

f(n) = 2^m, --> Eq(1) (EDITED on Feb 4, 2011 - This is actually proved by induction in the book so this guess for the value of f(n) , but this guess does work in providing the value of A(n) better than proving it by induction)

f(n) = 1 -->Eq(2) and

f(n) = n -->Eq(3) be your assumed functions . solving R with Eq(1) gives A(n)= 2^m --> Eq(4)

Solving R with Eq(2) gives A(n) - B(n) -C(n) = 1 -->Eq(5)

and solving R with Eq(3) gives A(n) + C(n) = n --> Eq(6)

**step 3**

solving these 3 equations (eqs 4,5 and 6) gives us the values of the coefficients . A(n) = 2^m

B(n) = 2^m -1 - l (the last is the letter "ell" )

and C(n) = l (the letter ell)

thus the closed form of the recurrence is A(n) alpha + B(n) beta + C(n) gamma = 2^m * alpha + (2^m - 1 -l) * beta + l*gamma now the question is how can we be sure that we guess the "right" functions in step 2 ? how do we know that f(n) = 1 is a "good " guess ? the answer is that if you guess "wrong" you won't be able to solve for that equation and will end up with an impossible equality . and

**that**is how the repertoire method works! happy repertoiring