Mathematical explanation for the Repertoire Method There are a few questions already about this method, which has stumped me for a long while. The process is explained, for instance, here: Repertoire Method Clarification Required ( Concrete Mathematics )
What I absolutely don't get is: What's the meaning of plugging in simple functions (which are not solutions) in the recurrence and how would that help finding what the right solution really is?
As I understand it, we have a function determined by a recurrence relation and we want to find a closed formula for it. The recurrence being linear, we assume this closed form is a linear combination of 3 other functions, with coefficients $\alpha, \beta$ and $ \gamma$. 
The first method suggested in the book is clear to me: set simple values for the constants, since the function will be the same for all of them, and try to guess A, B and C and prove it by induction. What I don't get is the "dual" repertoire method.
$f$ could be anything, but it's something fixed, so I don't see any meaning in this process of plugging in $f(n) = 1$. $f$ clearly is not 1. What is going on?
I expect everything coming down to seeing a vector space / module in two different ways and then somehow picking some basis vectors from each. However, I can't work out the right abstraction.
I'd like to ask for a very explicit top down explanation of this repertoire method, if possible with linear algebra vocabulary.
 A: I know this is kinda old, but other explanations given here are needlessly complex.
Basically, our goal is to find a general function f for any $\alpha$, $\beta$, and $\gamma$, given the recurrence
\begin{align}
f(1) &= \alpha\\
f(2n) &= 2f(n)+\beta\\
f(2n+1) &= 2f(n)+\gamma
\end{align}
and the knowledge that there are some functions $A$, $B$, and $C$ such that 
$$
f(n) = A(n) \alpha + B(n) \beta + C(n) \gamma.
$$
We can find such functions by looking at special cases where we know $\alpha$, $\beta$, and $\gamma$, and where $f$ is easy to compute. Then combine such equations to solve for $A$, $B$, and $C$. The book has the new $f$ value listed first, then derives the values of the variables which satisfy that equation, but for clarity I will begin by defining values for the variables, then wave my hand and get the function $f$ which satisfies the recurrence under those variables. The first case (in the book) has, 
\begin{align}
\alpha &= 1\\
\beta &= 0\\
\gamma &= 0\\
\end{align}
So that for $n=2^m+l$,
\begin{align}
f(n) = 2^m
\end{align}
Plugging in the values we get, 
\begin{align}
f(n) &= A(n) \alpha + B(n) \beta + C(n) \gamma\\
2^m &= A(n)
\end{align}
Next we make, 
\begin{align}
\alpha &= 1,\\
\beta &= -1,\\
\gamma &= -1.
\end{align}
So that, 
\begin{align}
f(n) = 1.
\end{align}
Plugging in the values we get, 
\begin{align}
f(n) &= A(n) \alpha + B(n) \beta + C(n) \gamma\\
1 &= A(n)-B(n)-C(n)
\end{align}
And finally we take, 
\begin{align}
\alpha &= 1\\
\beta &= 0\\
\gamma &= 1
\end{align}
So that, 
\begin{align}
f(n) = n
\end{align}
Plugging in the values we get,
\begin{align}
f(n) &= A(n) \alpha + B(n) \beta + C(n) \gamma\\
n&= A(n) + C(n)
\end{align}
Now we have, 
\begin{align}
A(n) &= 2^m\\
1 &= A(n) - B(n) -C(n)\\
n &= A(n) + C(n)
\end{align}
Remembering that $n = 2^m + l$ we get, 
\begin{align}
A(n) &= 2^m\\
B(n) &= 2^m -1-l\\
C(n) &= l\\
\end{align}
For a final equation of
\begin{align}
f(2^m+l) = 2^m\alpha + (2^m-1-l)\beta + l\gamma
\end{align}
QE-motherfunctioning-D!
