Results 1 to 8 of 8

Math Help - Reccurance relation

  1. #1
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1

    Reccurance relation

    How do you solve the following reccurance relation?

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

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Chris11 View Post
    How do you solve the following reccurance relation?

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

    Thanks.
    Inspection. 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 G(x)=\sum_{n=1}^{\infty}R_n x^n. Then, we get that \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 \sum_{n=1}^{\infty}nx^n=\frac{-x}{(1-x)^2} and so 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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    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).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Chris11 View Post
    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??
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by Drexel28 View Post
    Inspection. 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 G(x)=\sum_{n=1}^{\infty}R_n x^n. Then, we get that \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 \sum_{n=1}^{\infty}nx^n=\frac{-x}{(1-x)^2} and so 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 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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Sep 2009
    Posts
    177
    Thanks
    1
    Can you recomend to me a good book on reccurance? thanks
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by mr fantastic View Post
    Actually the solution is 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 R_0=0 since he didn't say anything.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,751
    Thanks
    651
    Hello, Chris11!

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


    Solve the following reccurance: . 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: . 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.

    . . \begin{array}{cccccccccc}<br />
\text{Sequence} & 2 && 4 && 7 && 11 && 16 \\<br />
\text{1st diff.} && 2 && 3 && 4 && 5 \\<br />
\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: . R(n) \:=\:an^2 + bn + c


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

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

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

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

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

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


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

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. Replies: 1
    Last Post: March 1st 2010, 07:24 AM
  3. Relation ( Equivalence Relation)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: December 5th 2008, 08:55 AM
  4. Can anyone solve this using reccurance relation!!!!!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 1st 2008, 03:22 AM
  5. Replies: 1
    Last Post: June 1st 2008, 12:34 AM

Search Tags


/mathhelpforum @mathhelpforum