1. ## Reccurance relation

How do you solve the following reccurance relation?

R(n)=R(n-1)+n?

Thanks.

2. Originally Posted by Chris11
How do you solve the following reccurance relation?

R(n)=R(n-1)+n?

Thanks.
Inspection. $\displaystyle R_n=n+R_{n-1}=n+n-1+R_{n-2}=\cdots=n+n-1+\cdots+1=\frac{n(n+1)}{2}$. Or, I guess if you're really picky you could do a generating function.

Let $\displaystyle G(x)=\sum_{n=1}^{\infty}R_n x^n$. Then, we get that $\displaystyle \sum_{n=1}^{\infty}R_{n-1}x^n=\sum_{n=0}^{\infty}R_nx^{n-1}=\sum_{n=1}^{\infty}R_nx^{n-1}+\frac{R_0}{x}=\frac{G(x)+R_0}{x}=\frac{G(x)}{x}$ and $\displaystyle \sum_{n=1}^{\infty}nx^n=\frac{-x}{(1-x)^2}$ and so $\displaystyle G(x)=\frac{G(x)}{x}-\frac{x}{(1-x)^2}\implies \left(1-\frac{1}{x}\right)G(x)=\frac{-x}{(1-x)^2}\implies G(x)=\frac{x^2}{1-x}$. And you can go from there...but inspection is better I think

3. I don't know anything about methods for solving recurance relations. I'm working on a problem right now and if I can solve the relation R(n)=R(n-1)+n with R(0)=2, R(1)=4, I'll be able to finish the problem.

I have this: R(n-1)=R(n-2)+n, I subtracted this from R(n)=R(n-1)+n and solved for R(n), getting R(n)=2R(n-1)-R(n-2).

4. Originally Posted by Chris11
I don't know anything about methods for solving recurance relations. I'm working on a problem right now and if I can solve the relation R(n)=R(n-1)+n with R(0)=2, R(1)=4, I'll be able to finish the problem.

I have this: R(n-1)=R(n-2)+n, I subtracted this from R(n)=R(n-1)+n and solved for R(n), getting R(n)=2R(n-1)-R(n-2).
What's wrong with my first method??

5. Originally Posted by Drexel28
Inspection. $\displaystyle R_n=n+R_{n-1}=n+n-1+R_{n-2}=\cdots=n+n-1+\cdots+1=\frac{n(n+1)}{2}$. Or, I guess if you're really picky you could do a generating function.

Let $\displaystyle G(x)=\sum_{n=1}^{\infty}R_n x^n$. Then, we get that $\displaystyle \sum_{n=1}^{\infty}R_{n-1}x^n=\sum_{n=0}^{\infty}R_nx^{n-1}=\sum_{n=1}^{\infty}R_nx^{n-1}+\frac{R_0}{x}=\frac{G(x)+R_0}{x}=\frac{G(x)}{x}$ and $\displaystyle \sum_{n=1}^{\infty}nx^n=\frac{-x}{(1-x)^2}$ and so $\displaystyle G(x)=\frac{G(x)}{x}-\frac{x}{(1-x)^2}\implies \left(1-\frac{1}{x}\right)G(x)=\frac{-x}{(1-x)^2}\implies G(x)=\frac{x^2}{1-x}$. And you can go from there...but inspection is better I think
Actually the solution is $\displaystyle R_n = k + \frac{n(n+1)}{2}$, where the first term (k is a constant) is the homogenous solution and the second term is the particular solution.

6. Can you recomend to me a good book on reccurance? thanks

7. Originally Posted by mr fantastic
Actually the solution is $\displaystyle R_n = k + \frac{n(n+1)}{2}$, where the first term (k is a constant) is the homogenous solution and the second term is the particular solution.
Yeah, I assumed that $\displaystyle R_0=0$ since he didn't say anything.

8. Hello, Chris11!

Your initial values don't work . . . I'll modify them.

Solve the following reccurance: .$\displaystyle R(n)\:=\:R(n-1)+n\;\;\;\text{ with: }R(1) = 2,\;R(2) = 4$
We can crank out the first few values of the sequence: .$\displaystyle 2,4,7,11,16, \hdots$

Take the difference of consecutive terms of the sequence,
. . then take the difference of the differences, and so on.

. . $\displaystyle \begin{array}{cccccccccc} \text{Sequence} & 2 && 4 && 7 && 11 && 16 \\ \text{1st diff.} && 2 && 3 && 4 && 5 \\ \text{2nd diff.} &&& 1 && 1 && 1 \end{array}$

We see that the second differences are constant.
. . Hence, the generating function is of the second degree, a quadratic.

The general quadratic function is: .$\displaystyle R(n) \:=\:an^2 + bn + c$

Use the first three values of the sequence and set up a system of equations:

. . $\displaystyle \begin{array}{ccccc} f(1)\,=\,2\!: & a + b + c &=& 2 & [1] \\ f(2) \,=\,4\!: & 4a + 2b + c &=& 4 & [2] \\ f(3) \,=\,7\!: & 9a + 3b + c &=& 7 & [3] \end{array}$ . . . Then solve this system.

. . $\displaystyle \begin{array}{ccccc} \text{Subtract [2] - [1]:} & 3a + b &=& 2 & [4] \\ \text{Subtract [3] - [1]:} & 5a + b &=& 5 & [5] \end{array}$

. . $\displaystyle \begin{array}{cccccccc} \text{Subtract [5] - [4]:} & 2a \:=\: 1 & \Rightarrow & \boxed{a \:=\:\tfrac{1}{2}} \end{array}$

Substitute into [4]: .$\displaystyle 3\left(\tfrac{1}{2}\right) + b \:=\:2 \quad\Rightarrow\quad \boxed{b \:=\:\tfrac{1}{2}}$

Substitute into [1]: .$\displaystyle \tfrac{1}{2} + \tfrac{1}{2} + c \:=\:2 \quad\Rightarrow\quad\boxed{ c \:=\:1}$

Therefore: .$\displaystyle R(n) \;=\;\tfrac{1}{2}n^2 + \tfrac{1}{2}n + 1 \;=\;\tfrac{1}{2}(n^2+n+2)$