# Find a recurrence relation and generating function of…

Model the amount of crab being caught per year based on the assumption that the # of crab caught in a year is the average of the # caught in the 3 preceding years.

a.) Find a recurrence relation for $C_n$, the # of crab caught in a year $n$.

For this I got:

$$C_n = {C_{n-1} + C_{n-2} + C_{n-3}\over 3}$$

b.) Find a generating function: $$f(x)= \sum_{n≥1} C_nx^n$$ With initial conditions $C_1 = 1$, $C_2 = 2$ and $C_3 = 2$.

We had gone over the auxiliary equation and the generating function methods in class but I am not sure how to proceed after my recurrence relation, any help is appreciated.

• Sorry if I misunterpret the question: do you want to find a closed-form expression for the generating function, or a representation as infinite sum? – Clement C. Dec 7 '15 at 19:55

Let the generating function of $f$ be given by $f(x)=\sum_{n=1}^\infty C_n x^n$. Then, \begin{align} 3f(x)&=3(C_1x+C_2x^2+C_3x^3)+\sum_{n=4}^\infty 3C_n x^n = 3(x+2x^2+2x^3)+\sum_{n=4}^\infty (C_{n-1}+C_{n-2}+C_{n-3}) x^n \\ &= 3(x+2x^2+2x^3)+x\sum_{n=4}^\infty C_{n-1}x^{n-1} +x^2\sum_{n=4}^\infty C_{n-2}x^{n-2}+x^3\sum_{n=4}^\infty C_{n-3}x^{n-3}\\ &= 3x+6x^2+6x^3+x\sum_{n=3}^\infty C_{n}x^{n} +x^2\sum_{n=2}^\infty C_{n}x^{n}+x^3\sum_{n=1}^\infty C_{n}x^{n} \\ &= 3x+6x^2+6x^3+x(f(x)-x-2x^2) +x^2(f(x)-x)+x^3f(x) \\ &= 3x+6x^2+6x^3-x^2-2x^3 -x^3+(x+x^2+x^3)f(x) \\ &= 3x+5x^2+3x^3+(x+x^2+x^3)f(x) \\ \end{align} so $$f(x) = \frac{3x+5x^2+3x^3}{3-x-x^2-x^3}$$ (wherever it is well-defined, i.e. $x\neq 3$)