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
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).
Hello, Chris11!
Your initial values don't work . . . I'll modify them.
We can crank out the first few values of the sequence: .$\displaystyle 2,4,7,11,16, \hdots$Solve the following reccurance: .$\displaystyle R(n)\:=\:R(n-1)+n\;\;\;\text{ with: }R(1) = 2,\;R(2) = 4$
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) $