Results 1 to 7 of 7

Math Help - Recurrence relation ( Advanced counting Techniques)

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    26

    Recurrence relation ( Advanced counting Techniques)

    A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years.

    (a) Find a recurrence relation for {Pn}, where Pn is the number of lobsters caught in year n, under the assumption for this model.

    (b) Find Pn if 100000 lobsters were caught in year 1 and 300000 were caught in year 2.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    P_{n+2}=\frac{P_n + P_{n+1}}{2}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,689
    Thanks
    617
    Hello, bhuvan!

    I know some techniques for this problem.
    I hope they're appropriate for your course.


    A model for the number of lobsters caught per year is based on the assumption
    that the number of lobsters caught in a year is the average of the number
    caught in the two previous years.

    (a) Find a recurrence relation for P(n), the number of lobsters caught in year n.

    . . P(n) \;=\;\frac{P(n-1) + P(n-2)}{2}




    (b) Find P(n) if P(1) = 100,\!000\text{ and }P(2) = 300,\!000.

    From (a), we have: . 2P(n) \;=\;P(n-1) + P(n-2) .[1]

    We conjecture that P(n) is an exponential function: . P(n) \,=\,X^n

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

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

    . . And we have two roots: . X \;=\;1,\;\text{-}\tfrac{1}{2}

    Then: . f(n) = 1^n\:\text{ or }\:f(n) = \left(\text{-}\tfrac{1}{2}\right)^n


    Form a linear combination of these roots:
    . . f(n) \;=\;A\left(1^n\right) + B\left(\text{-}\tfrac{1}{2}\right)^n \quad\Rightarrow\quad f(n) \;=\;A + B\left(\text{-}\tfrac{1}{2}\right)n


    We know the first two values of this sequence:

    . . \begin{array}{ccccc}<br />
f(1) = 100,\!000\!: & A - \frac{1}{2}B &=& 100,\!000 & {\color{blue}[2]} \\ \\[-3mm]<br />
f(2) = 300,\!000\!: & A + \frac{1}{4}B &=& 300,\!000 & {\color{blue}[3]} \end{array}

    Subtract [2] from [3]: . \tfrac{3}{4}B \:=\:200,\!000 \quad\Rightarrow\quad B \:=\:\frac{800,\!000}{3}

    Substitute into [3]: . A + \tfrac{200,\!000}{3} \:=\:300,000 \quad\Rightarrow\quad A \:=\:\frac{700,\!000}{3}


    Therefore: . f(n) \;=\;\frac{700,\!000}{3} + \frac{800,\!000}{3}\left(\text{-}\frac{1}{2}\right)^n  \quad\Rightarrow\quad f(n) \;=\;\frac{100,\!000}{3}\bigg[7 + \frac{8}{(\text{-}2)^n} \bigg]

    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2008
    Posts
    26
    Thanks you very much !!

    Do you know how to solve below problem i am trying to solve this but i am confuse..

    Consider the non homogeneous linear recurrence relation an=2an-1+2^n

    (a) show that an=n2^n is a solution of this relation.

    i tried to solve this by putting an value in

    2an-1+2^n=2(n2^n)+2^n)=2^n(2n+1) but i am not getting right answer as far as i think.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    It works !
    2a_{n-1}+2^n=2(n-1)2^{n-1}+2^n=2n2^{n-1}-2.2^{n-1}+2^n=n2^n=a_n
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2008
    Posts
    26
    can you please explain it ? i am confuse how you got 2(n-1)2^n-1
    in 2(n-1)2^n-1+2^n since we have an=n2^n ??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2008
    Posts
    26
    Never mind i got it.. Thank You for your effort.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recurrence relation dealing with counting out bills
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 13th 2010, 08:45 PM
  2. Counting Techniques.
    Posted in the Statistics Forum
    Replies: 3
    Last Post: October 24th 2009, 03:14 PM
  3. Probability Probelms & Counting Techniques
    Posted in the Statistics Forum
    Replies: 11
    Last Post: June 10th 2008, 08:03 PM
  4. Data Help!!! Counting Techniques
    Posted in the Statistics Forum
    Replies: 2
    Last Post: March 3rd 2008, 03:33 PM
  5. Advanced Integration Techniques Textbook?
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: March 11th 2006, 03:29 PM

Search Tags


/mathhelpforum @mathhelpforum