# Solving this recursive equations

I have these recursive equations in Combinatorics and I need to find $a_n$

\begin{align} a_n & = 2b_{n-1} + 2c_{n-1} \\ b_n & = a_{n-1} + c_{n-1} \\ c_n & = a_{n-1} + c_{n-1} + b_{n-1} \end{align}

I tried alot of ways and could not get an independent equation for $a_n$.

-
One can use Equation 2 to transform Equations 1 and 3 into a system in $a$ and $c$ only. Did you try this? – Did Apr 28 '13 at 7:10
I managed to get this: $a_n = 4b_{n-1} + 2b_{n-2}$ – TheNotMe Apr 28 '13 at 7:19
Which seems clearly wrong. You might want to expand on the way you got this. – Did Apr 28 '13 at 7:27

## 2 Answers

From (1) and (2): $$b_n = 2b_{n-2} + 2c_{n-2} + c_{n-1}\ \ \ \ \ \ (4)$$

From (2) and (3): $$c_n - b_{n} =b_{n-1} \ \ \ \ \ \ (5)$$

Now substitute $c_n$ from (5) to (4).

.

-

Define: $A(z) = \sum_{n \ge 0} a_n z^n$ and so on. Write: \begin{align*} a_{n + 1} &= 2 b_n + 2 c_n \\ b_{n + 1} &= a_n + c_n \\ c_{n + 1} &= a_n + b_n + c_n \end{align*} By the properties of generating functions: \begin{align*} \frac{A(z) - a_0}{z} &= 2 B(z) + 2 C(z) \\ \frac{B(z) - b_0}{z} &= A(z) + C(z) \\ \frac{C(z) - c_0}{z} &= A(z) + B(z) + C(z) \end{align*} We are just interested in the solution for $A(z)$ in the resulting linear system: $$A(z) = \frac{a_0 - (a_0 - 2 b_0 - 2 c_0) z - (a_0 - 2 c_0) z^2} {1 - z - 5 z^2 - 2 z^3}$$ Next step would be split this into partial fractions, and expand the fractions. But the factors of the denominator are quite ugly.

-