Find and solve a recurrence relation for the number of ways to make a pile of $n$ poker chips using red, white, and blue chips and such that no two red chips are together (consecutive).
I believe I have found the recurrence relation correctly, however it is solving it where I am running into problems
Part $1)$ Find a recurrence relation
Consider the color of the top chip, if it is red, then he one below cannot be red and the remaining $n-2$ chips give $a_{n-2}$ different ways.
If it is not red, then the remaining $n-1$ chips give $a_{n-1}$ different ways. Then I believe my recurrence relation is
$$a_n = 2a_{n-1}+2a_{n-2}$$
with $a_1=3, a_2=8$
- If you have two poker chips you have 8 ways to make a pile without two consecutive red chips: $wb,bw,rw,wr,rb,br,ww, bb$. Or you calculate all possible ways and substract the $rr$ combination: $a_2=3^2-1=8$
- Similar for $a_1$: The are 3 ways without two consecutive red chips: $r,b,w\Rightarrow a_1=3$
Part $2)$ Solve the recurrence relation
Using the characteristic equation,
$$x^n = 2x^{n-1}+2^{n-2}$$
Dividing by the smallest power gives,
$$x^2-2x-2=0$$
Solving for $x$ gives,
$$x = 1 \pm \sqrt3$$
Then using the general solution:
$$a_n = A_1x_1^{n+1}+A_2x_2^{n+1}$$
Using conditions from above,
$$ 3 = A_1(1+\sqrt3)^2+A_2(1-\sqrt3)^2$$ $$ 8 = A_1(1+\sqrt3)^3+A_2(1-\sqrt3)^3$$
Solving for $A_1, A_2$ I got $A_1 = b=\frac{3+\sqrt{3}}{12}, A_2 = b=\frac{3-\sqrt{3}}{12}$
Therefore the final answer would be
$$a_n = \frac{3+\sqrt{3}}{12}(1+\sqrt3)^{n+1} + \frac{3-\sqrt{3}}{12}(1-\sqrt3)^{n+1}$$
However an answer I found online to this question is the following, so I am not sure where I went wrong in solving it, looking for some help thanks!
$$a_n = \frac{1}{4\sqrt3}\left[ (1+\sqrt3)^{n+2} - (1-\sqrt3)^{n+2}\right]$$
Your solution and the online answer are both correct. Note that your exponents are one higher than the online answer, so split out the extra factor and note that $$\frac {1+\sqrt 3}{4\sqrt 3}=\frac {\sqrt 3+3}{12},\frac {1-\sqrt 3}{4\sqrt 3}=\frac {\sqrt 3-3}{12}$$