Recurrence relation ( Advanced counting Techniques)

Printable View

Nov 28th 2008, 09:39 AM
bhuvan

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.
Nov 28th 2008, 11:14 AM
running-gag

$P_{n+2}=\frac{P_n + P_{n+1}}{2}$
Nov 28th 2008, 11:40 AM
Soroban

Hello, bhuvan!

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

Quote:

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}$

Quote:

(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]$
Nov 28th 2008, 12:04 PM
bhuvan

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.
Nov 28th 2008, 12:09 PM
running-gag

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$
Nov 28th 2008, 12:31 PM
bhuvan

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 ??
Nov 28th 2008, 12:42 PM
bhuvan

Never mind i got it.. Thank You for your effort.