Repertoire Method. How to know when equations are valid

Question

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.

Answer 1

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}$$

Answer 2

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.