# Finding a Linear Recurrence Relation

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 $L_n$, where $L_n$ is the number of lobsters caught in year n, under the assumption for this model.

My answer: $$L_n = \frac{1}{2}L_{n-1} + \frac{1}{2}L_{n-2}$$

b) Find $L_n$ if $100,000$ lobsters were caught in year $1$ and $300,000$ were caught in year $2$.

My Answer: The characteristic equation is $$r^2 - \frac{1}{2}r - \frac{1}{2} = 0$$ and $$\frac{1}{2}(2r+1)(r-1) = 0$$

The roots are $r=-\frac{1}{2}$ and $r=1$.

The general solution is $$L_n = k_1\left(-\frac{1}{2}\right)^n + k_2.$$

Considering the initial conditions, we have: $$-\frac{1}{2}k_1 + k_2 = 100000 \quad\mbox{and}\quad \frac{1}{4}k_1 + k_2 = 300000$$

Solving this system of equations, we have $$k_1 =\frac{800000}{3}$$ $$k_2 = \frac{700000}{3}$$ and

$$L_n = \frac{800000}{3}\left(-\frac{1}{2}\right)^n + \frac{700000}{3}.$$

Is this right? Thank you!

-
I love lobster. Your typesetting, less... This could be useful in the future. – 1015 Apr 14 '13 at 22:21
I tried to fix it..better? – tekman22 Apr 14 '13 at 22:28
Much better! I did the rest. So for instance 1/2 can be written \frac{1}{2}. – 1015 Apr 14 '13 at 22:32
Regarding the proof, it looks good to me. – 1015 Apr 14 '13 at 22:34

OK, use generating functions (just for fun). The recurrence is: $$L_{n + 2} = \frac{1}{2} (L_{n + 1} + L_n) \qquad L_1 = 100000, L_2 = 300000$$ Define the generating function: $$A(z) = \sum_{n \ge 1} L_n z^{n - 1}$$ By the properties of generating functions: $$\frac{A(z) - L_1 - L_2 z}{z^2} = \frac{1}{2} \frac{A(z) - L_1}{z} + \frac{1}{2}A(z)$$ As partial fractions: $$A(z) = \frac{700000}{3} \frac{1}{1 - z} - \frac{400000}{3} \frac{1}{1 + z / 2}$$ Expanding the geometric series: $$L_n = \frac{700000}{3} - \frac{400000}{3} \left( - \frac{1}{2} \right)^{n - 1} = \frac{700000}{3} - \frac{800000}{3} \left( - \frac{1}{2} \right)^n$$