Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
(Off-topic remark: It's a gamma ($\gamma$) and not an epsilon ($\epsilon$). –  Hans Lundmark Sep 27 '11 at 15:00
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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. –  Rire1979 Sep 28 '11 at 8:23
    
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$. –  Hans Lundmark Sep 28 '11 at 8:29
    
(Where I expanded $(n-1)^2=n^2-2n+1$ of course.) –  Hans Lundmark Sep 28 '11 at 8:31
    
Nevermind, I got it :). Oh, thanks anyway. :) –  Rire1979 Sep 28 '11 at 8:31
    
how can you be sure that the solution is of the form A(n)alpha..... –  user39338 Sep 3 '12 at 13:28
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.