Repertoire Method. How to know when equations are valid I'm trying to work a few examples from the Repertoire Method from the Book Concrete Mathematics.
I'm working through the following recurrence:
$f(0) = 1$
$f(n) = 2f(n-1) + n$
Which I generalized as:
$f(0) = \alpha$
$f(n) = 2f(n-1) + \beta n$
My goal is to find the closed solution for f(n) for the generalized recurrence. 
The first few solutions are:
$0 => \alpha$
$1 => 2 \alpha + \beta$
$2 => 4 \alpha + 4 \beta$
$3 => 8 \alpha + 8 \beta$
$4 => 16 \alpha + 25 \beta$
So it seems like I can rewrite my recurrence as:
$f(n) = A(n) \alpha + B(n) \beta$
$A(n)$ is certainly $2^n$, so $f(n) = \alpha 2^n + \beta B(n)$. The next step is I try to set f(n) to some simple function, and try to find the value of $B(n)$. For example, when $f(n) = 1$:
$1 = \alpha$
and
$1 = 2 + \beta n$
Then $\alpha = 1$ and $\beta = -1/n$
So $2^n - 1/n * B(n) = 1$ means $B(n) = -n + n2^n$. But this function is clearly wrong, in fact $B(2) = 6$ instead of 4, which is what I expected.
I guess my question is, how do I know that setting $f(n) = 1$ does not help me solve the equation? Is it because $\beta$ depends on $n$ for its value?
EDIT:
I think now I understand that $\beta$ has to be a constant.
 A: As you have noticed, you can easily prove by induction that $f(n)=A(n)\alpha+B(n)\beta$. We can use the recurrence relation on $f$ to find relations for $A$ and $B$:
$$A(n)\alpha+B(n)\beta = f(n) = 2f(n-1)+\beta n = 2A(n-1)\alpha+(2B(n-1)+n)\beta$$
and thus:
$$A(n)=2A(n-1)$$
$$B(n)=2B(n-1)+n$$
With initial conditions given by $f(0)=\alpha\Rightarrow A(0)=1,\ B(0)=0$ we get that $A(n)=2^n$ and that $B(n)$ solves the generalized recurrence with $\alpha=0$ and $\beta=1$. You can check that the solution to this recurrence is given by
$$B(n)=2^nB(0)+\sum_{k=0}^n2^{n-k}k = \sum_{k=0}^n2^{n-k}k$$
Its generating function should be:
$$\sum_{n=0}^\infty B(n)x^n=\frac{-x}{(1-2x)(1-x)^2}$$
A: Another way (difference equations):
$$
f(k)= \alpha f(k-1)+ \beta k\\
f(k+1)= \alpha f(k)+ \beta (k+1)\\
f(k+1)-f(k)=\alpha (f(k)-f(k-1))+\beta
$$
Denote $F(k+1)=f(k+1)-f(k)$, hence
$$
F(k+1)= \alpha F(k)+\beta=\alpha^2F(k-1)+\alpha \beta+\beta \\
=\alpha^3F(k-2)+\alpha^2 \beta+\alpha \beta + \beta\\
\ldots\\
=\alpha^{k}F(1)+\beta\sum_{j=0}^{k-1}\alpha^{j}=\alpha^{k}F(1)+\frac{\beta}{1-\alpha}-\frac{\beta \alpha^{k}}{1-\alpha}
$$
Now if you sum over $k$, you get a telescoping sum on LHS:
$$
\sum_{k=0}^{n}F(k+1)=\sum_{k=0}^{n}(f(k+1)-f(k))=f(n+1)-f(0)
$$
And the result becomes
$$
f(n+1)=f(0)+(f(1)-f(0)) \cdot \frac{1-\alpha^{n+1}}{1-\alpha} + \frac{n \beta}{1-\alpha}-\frac{\beta}{1-\alpha}\cdot \Bigg(\frac{1-\alpha^{n+1}}{1-\alpha}\Bigg)
$$
Since you know $f(0)$ amd $f(1)$, you are done. 
