Results 1 to 7 of 7

Math Help - How to solve this recurrence relation ?

  1. #1
    Newbie
    Joined
    Apr 2009
    Posts
    4

    How to solve this recurrence relation ?

    3P(n) = 1-P(n-1).
    P(n) = ???
    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by denniszeng2008@gmail.com View Post
    3P(n) = 1-P(n-1).
    P(n) = ???
    Thanks in advance.
    Could you please post the complete question.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2009
    Posts
    4

    Complement

    it is only a recursive problem.
    3P(n) = 1 - P(n-1)
    3P(n-1) = 1 - P(n - 2)
    ...
    How to figure out P(n) = ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jan 2009
    Posts
    591
    Quote Originally Posted by denniszeng2008@gmail.com View Post
    3P(n) = 1-P(n-1).
    P(n) = ???
    Thanks in advance.
    if
    3P(n) = 1-P(n-1)

    then
    P(n) = (1-P(n-1))/3
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2009
    Posts
    4

    But

    But i want to figure out a p(n) = n 's function but not a recurrence sequence.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,683
    Thanks
    615
    Hello, denniszeng!

    3\!\cdot\!P(n) \:=\: 1-P(n-1)\qquad\text{Find }P(n)
    Let P(n) \:=\:X^n

    \begin{array}{cccccc}\text{Then we have:} &3X^n &=& 1-X^{n-1} & [1] \\ \text{The next term:} & 3X^{n+1} &=& 1 - X^n & [2] \end{array}

    Subtract [2] - [1]: . 3X^{n+1} -3X^n \:=\:-X^n + X^{n-1} \quad\Rightarrow\quad X^{n+1} - 3X^n - X^{n-1} \:=\:0

    Divide by X^{n-1}\!:\;\;3X^2 -2X - 1 \:=\:0 \quad\Rightarrow\quad (X-1)(3X+1) \:=\:0

    . . Hence: . X \:=\:1,\:\text{-}\tfrac{1}{3}

    Then P(n) is of the form: . P(n) \;=\;A(1^n) + B\left(\text{-}\tfrac{1}{3}\right)^n

    . . That is: . P(n) \:=\:A + B\frac{(\text{-}1)^n}{3^n} .[3]


    Suppose the first term is a\!:\;\;P(1) \:=\:a

    Then the second term is: P(2) \:=\:\tfrac{1}{3}(1-a)


    Substitute into [3]:

    . . \begin{array}{ccccccc}P(1) \:=\:a\!:& & A - \frac{B}{3}&=& a \\ \\[-4mm] <br />
P(2) \:=\:\frac{1}{3}(1-a)\!: && A + \frac{B}{9} &=& \frac{1}{3}(1-a) \end{array}


    Solve the system: . A \:=\:\frac{1}{4},\quad B \:=\:\tfrac{3}{4}(1 - 4a)


    Therefore: . P(n) \;=\;\frac{1}{4} + \frac{3}{4}(1-4a)\frac{(\text{-}1)^n}{3^n} \;=\;\frac{1}{4}\left[1 + (\text{-}1)^n\,\frac{3(1-4a)}{3^n}\right]

    . . . . . . . . P(n) \;=\;\frac{1}{4}\left[1 + (\text{-}1)^n\frac{1-4a}{3^{n-1}}\right]

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2009
    Posts
    4
    But Why P(n) can have that form relate to 1 and 1/3 ?
    since it is only a special example we pick that p(n) = x^n
    Thanks very much!

    I don't want to only know the solution, can you teach me how to analyze this ?
    When i encounter such a problem, what should i do to figure out the right solution ?
    Thanks
    Last edited by mr fantastic; April 19th 2009 at 08:54 PM. Reason: Merged posts
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. big o recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 4th 2011, 03:49 AM
  2. Solve the recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 10th 2010, 05:16 AM
  3. Solve the recurrence relation
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: May 15th 2010, 05:03 PM
  4. Help with recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 10th 2010, 04:24 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 08:02 AM

Search Tags


/mathhelpforum @mathhelpforum