Results 1 to 7 of 7

Thread: 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
    $\displaystyle 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
    12,028
    Thanks
    848
    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 $\displaystyle P(n)$, the number of lobsters caught in year $\displaystyle n.$

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




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

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

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

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

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

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

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


    Form a linear combination of these roots:
    . . $\displaystyle 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:

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

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

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


    Therefore: .$\displaystyle 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 !
    $\displaystyle 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: Apr 13th 2010, 08:45 PM
  2. Counting Techniques.
    Posted in the Statistics Forum
    Replies: 3
    Last Post: Oct 24th 2009, 03:14 PM
  3. Probability Probelms & Counting Techniques
    Posted in the Statistics Forum
    Replies: 11
    Last Post: Jun 10th 2008, 08:03 PM
  4. Data Help!!! Counting Techniques
    Posted in the Statistics Forum
    Replies: 2
    Last Post: Mar 3rd 2008, 03:33 PM
  5. Advanced Integration Techniques Textbook?
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: Mar 11th 2006, 03:29 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum