Levelling up in Math land

(Edited on Feb 4 2011), This entry is correct but is now obsolete.I rewrote this with more detail here. Please use that instead.

Concrete Mathematics is a fine book. But in the very first there is a bit of handwaving that goes on to eventually get seemingly magical and the novice who is using the book for self study (iow, someone like me ) can get lost very easily .

A good example is the "solving a rcurrence by the repertoire method " explanation on pages 12 - 15 ). A margin note by a student (an excellent idea to include these) warns us "Beware . authors expect us to figure out the idea of the repertoire method by seat-of-the-pant examples instead of giving us a top down presentation " .

Unfortunately that doesn't help a reader to figure out what is going on and how to use the "repertoire method " to solve a recurrence . I've been banging my head against this for a few hours and i think i found out how the repertoire method works . here it is .

I will use the same recurrence the authors use .

Recurrence R =

f(1) = alpha
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