# Thread: Explaination for the 'repertoire method' for solving recurrences/sums?

1. ## Explaination for the 'repertoire method' for solving recurrences/sums?

Repertoire method to solve summation, where in you express the sum as a function of some constant times some function of n, like A(n) etc... I am trying to follow 'Concrete Mathematics', by Graham and Knuth, but having some difficulties in understanding these techniques which they applied to solve Josephus problem, could anybody explain please, giving an example....

2. please any replies!

3. Perhaps my question was not exact..
here is a problem.

Solve the recurrence
$\displaystyle Q_0 = \alpha;$
$\displaystyle Q_1 = \beta;$
$\displaystyle Q_n = (1 + Q_ {n-1}\ )/Q_ {n-2}$, for $\displaystyle n \geq 1.$

Assume that $\displaystyle Q_n \ != 0$ for all $\displaystyle n \geq 0$.

How do you do this, specifically I need to do this usuing 'repertoire method', that is assuming
$\displaystyle Q_n = A(n)\alpha + B(n)\beta + C(n) \gamma$
Although what equation I wrote above may not be right, since I don't understand such assumption, amd thus I need help....
Please...

4. Originally Posted by natarajchakraborty
Perhaps my question was not exact..
here is a problem.

Solve the recurrence
$\displaystyle Q_0 = \alpha;$
$\displaystyle Q_1 = \beta;$
$\displaystyle Q_n = (1 + Q_ {n-1}\ )/Q_ {n-2}$, for $\displaystyle n \geq 1.$

Assume that $\displaystyle Q_n \ != 0$ for all $\displaystyle n \geq 0$.

How do you do this, specifically I need to do this usuing 'repertoire method', that is assuming
$\displaystyle Q_n = A(n)\alpha + B(n)\beta + C(n) \gamma$
Although what equation I wrote above may not be right, since I don't understand such assumption, amd thus I need help....
Please...
/****************/
The key idea is value of function and constants not matter!
Only we want to know, how many constants are there.
If we find this answer we will also know the value of given recurrence.
Thats it!
/****************/

,

,

### "repertoire method " math

Click on a term to search for related topics.