17
$\begingroup$

In the book Concrete Mathematics, chapter 2, section 2.2 -- sums and recurrences, page 26 (2nd edition), the authors talk about the following example:

Given the general recurrence

$$ R(0) = \alpha $$ $$ R(n) = R(n-1) + \beta + \epsilon n $$

The authors generalize the recurrence relation to:

$$ R(n) = A(n)\alpha + B(n)\beta + C(n)\epsilon $$

Employing the Repertoire Method, the authors plug in simple functions of $n$ in order to determine $A(n), B(n), C(n)$. So they discover:

Setting $R(n) = 1$ implies $\alpha = 1, \beta = 0, \epsilon = 0 \implies A(n) = 1$.

Setting $R(n) = n$ implies $\alpha = 0, \beta = 1, \epsilon = 0 \implies B(n) = n$.

Setting $R(n) = n^2$ implies $\alpha = 0, \beta = -1, \epsilon = 0 \implies C(n) = \frac{n^2 + n}{2}$.

Values for the first couple of terms of the recurrence:

$$ \begin{eqnarray*} R(0) &=& \alpha \\ R(1) &=& \alpha + \beta + \epsilon \\ R(2) &=& \alpha + 2\beta + 3\epsilon \\ R(3) &=& \alpha + 3\beta + 6\epsilon \\ R(4) &=& \alpha + 4\beta + 10\epsilon \\ R(5) &=& \alpha + 5\beta + 15\epsilon \end{eqnarray*} $$

I do not understand what is the process through which the values for $\alpha$, $\beta$, and $\epsilon$ are implied. I would like some help with that. Where exactly do we look and what do we math them against to see what they have to be?

  • 4
    (Off-topic remark: It's a gamma ($\gamma$) and not an epsilon ($\epsilon$).2011-09-27

1 Answers 1

13

Put $R_n=1$ (for all $n$; hence also $R_0$ and $R_{n-1}$ should be set equal to 1) in (2.7): $$ 1 = \alpha, \quad 1 = 1 + \beta + \gamma n. $$ The first equation tells us $\alpha$ right away, and the second equality holds for all $n$ iff $\beta=\gamma=0$.

Then put $R_n=n$ (hence $R_0=0$ and $R_{n-1}=n-1$) in (2.7): $$ 0 = \alpha, \quad n = (n-1)+\beta + \gamma n. $$ Here $\beta=1$ and $\gamma=0$ is required for the identity to hold for all $n$ (compare coefficients for the constant terms and for the $n$-terms separately).

Etc.

  • 0
    What I don't get is that when choosing higher order functions for Rn, ie. Rn = n^2, I don't see how alpha, beta, and gamma can be guessed since there's no n^2 term in the right hand side of the equation.2011-09-28
  • 2
    With $R_n=n^2$ you get $0^2=\alpha$ and $n^2=(n-1)^2 + \beta + \gamma n$. In other words: $\alpha=0$ and $n^2 = n^2 + (\gamma-2)n + (1 + \beta)$, so that $\beta=-1$ and $\gamma=2$.2011-09-28
  • 0
    (Where I expanded $(n-1)^2=n^2-2n+1$ of course.)2011-09-28
  • 0
    Nevermind, I got it :). Oh, thanks anyway. :)2011-09-28
  • 0
    how can you be sure that the solution is of the form A(n)alpha.....2012-09-03
  • 0
    @faw: Because the recurrence itself depends linearly on $\alpha$, $\beta$ and $\gamma$. Isn't it pretty obvious from the first few $R(n)$'s written down in the question that they will be of the form $(\text{something}) \cdot \alpha + (\text{something}) \cdot \beta + (\text{something}) \cdot \gamma$?2012-09-04
  • 0
    @HansLundmark: I can see that it will be a combination of those, but I don't understand how we know A, B, and C will always be the same, which I have opened as a [new question](http://math.stackexchange.com/questions/551883/concrete-mathematics-stability-of-definitions-in-the-repertoire-method).2013-11-04