Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
1  
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
1  
Which seems clearly wrong. You might want to expand on the way you got this. –  Did Apr 28 '13 at 7:27

2 Answers 2

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).

.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.