Counting Polar Bears

Question

My class is starting to work with generating functions, and I've been working on a problem related to the counting of polar bears. Suppose that there is this bar that polar bears really like to get drinks at, and the bartender has been noticing a trend in the polar bears coming into his bar. Say at time 0, there are no bears at the bar, at time 1, there are 3 bears at the bar, and for every time $t \geq 2,$ The number of bears in the bar is equal to 5 times the number of bears in the bar at time $t-1$ plus the numbers of bears in the bar at time $t-2$ I want to find a close form expression for $P_n$, which is the number of bears in the bar at time $n.$ I get that I need to start this problem with considering the generation function $P(x)$ and that formally $P_0 = 0,P_1 = 3$, and $P_n = 5P_{n-1} + P_{n-2}$ for $n \geq 2.$ I'm wondering if it might be good to make $P_{n-1}$ and $P_{n-2}$ functions of the main generating function $P(x).$

Answer 1

You could just solve the recurrence directly. You have $P_{n+2} -5P_{n+1} -P_n = 0$, the eigenvalues are the roots of $x^2-5x-1 = 0$ which we can compute as ${1 \over 2} (5 \pm \sqrt{29})$. Hence the general solution is $P_n = \left({5 + \sqrt{29} \over 2}\right)^n c_0 + \left({5 - \sqrt{29} \over 2}\right)^n c_1$ for some constants $c_0,c_1$. Since $P_0 = 0$ we have $c_1 = -c_0$ and from $P_1 = 3$ we get $c_0 = {3 \over \sqrt{29}}$.

Hence $P_n = {3 \over \sqrt{29}} \left(\left({5 + \sqrt{29} \over 2}\right)^n - \left({5 - \sqrt{29} \over 2}\right)^n\right)$.

Answer 2

As usual, define $$ P(x) = \sum_{k=0}^\infty P_n x^n $$ and apply your identity: $$ P(x) = \sum_{k=0}^\infty P_n x^n = 3x + 5 \sum_{k=2}^\infty P_{n-1} x^n + \sum_{k=2}^\infty P_{n-2} x^n $$ Notice that the last sum is $$ \sum_{k=2}^\infty P_{n-2} x^n = x^2 \sum_{k=2}^\infty P_{n-2} x^{n-2} = x^2 \sum_{k=0}^\infty P_n x^n = x^2 P(x) $$

Can you transform the other sum and solve for $P(x)$?